Chapter 8.3, Problem 21E

Suppose that the function f satisfies the recurrence relation $f\left(n\right)=2f\left(\sqrt{n}\right)+1$ , whenever n is a perfect square greater than 1 and $\begin{array}{l}\\ f\left(2\right)=1\end{array}$ .

a) Find f(16).

b) Give a big-O estimate for $f\left(n\right)$. [Hint: Make the substitution $m=\log n$ .]