# Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen:

Suppose the function $$f$$ satisfies the recurrence relation $$f(n)=2f(\sqrt{n})+\log n$$ whenever $$n$$ is a perfect square greater than 1 and $$f(2)=1$$.

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

(Note: here, $$\log n$$ stands for base 2 logarithm of $$n$$.)

In this solution, I am supposed to use the following variant of the Master Theorem:

Master Theorem. Let $$f$$ be an increasing function that satisfies the recurrence relation

$$f(n)=af(n/b)+cn^d$$

whenever $$n=b^k$$, where $$k$$ is a positive integer, $$a\geq 1$$, $$b$$ is an integer greater than 1, and $$c$$ and $$d$$ are real numbers with $$c$$ postive and $$d$$ nonnegative. Then

\begin{align}f(n)&\text{is }\begin{cases} O(n^d)&\text{ if a < b^d,} \\ O(n^d\log n)&\text{ if a = b^d,} \\ O(n^{\log_b a})&\text{ if a > b^d.} \end{cases}\end{align}

I solved it as follows, but I'm not sure if this is correct:

Following the hint given, I made the substitution $$m = \log n$$. Then, $$n=2^m$$. Rewriting the recurrence relation with this value for $$n$$:

$$f(2^m)=2f(\sqrt{2^m})+\log (2^m)\text{ with }f(2)=1$$

$$f(2^m)=2f(2^{m/2})+m\text{ with }f(2)=1$$

(because $$\sqrt{2^m}=2^{m/2}$$ and $$\log (2^m)=m$$.)

To simplify the analysis, I will rewrite the recurrence relation above for $$T(m)=f(2^m)$$:

$$T(m)=2T(\dfrac{m}{2})+m\text{ with }T(1)=1$$

Now I will apply the Master Theorem for $$T(m)$$. In this case, $$d=1$$, $$b=2$$ and $$a=2$$, this recurrence relation meets the condition $$a=b^d$$ in the Master Theorem; therefore:

$$T(m)\text{ is }O(m^d\log m)=O(m\log m)$$

Now I will rewrite the estimate above in terms of $$f(n)$$, substituting $$T(m)=f(2^m)=f(2^{\log n})=f(n)$$ and $$m=\log n$$:

$$f(n)\text{ is } O(\log n\log \log n)$$

Is this solution correct? If yes, is there any way to simplify it further?

• Is $f(n)$ well defined when $n\neq2$ is not a perfect square? Jul 15, 2012 at 2:55
• @FrankScience: In this exercise, it seems that it's not.
– favq
Jul 15, 2012 at 22:33

Let's use recursion trees (otherwise known as "the proof of the Master theorem")!

• The root of the recursion tree for $f(n)$ has value $\log n$.

• Each child of the root has value $\log \sqrt{n} = (\log n)/2$, so the total value of all nodes at depth $1$ is also $\log n$.

• (Sanity check:) Each grandchild of the root has value $\log \sqrt{\sqrt{n}} = (\log n)/4$. So the total value of all $4$ nodes at level $2$ is also $\log n$.

• An easy inductive argument implies that for any $\ell$, the total value of the $2^\ell$ nodes at level $\ell$ is $\log n$.

• Thus, all level sums are identical, which implies that $f(n) = \Theta(L\log n)$, where $L$ is the number of levels.

• Another easy inductive argument implies that each subtree rooted at level $L$ represents the function $f(n^{2^{-L}})$. So the recursion bottoms out at the smallest level $L$ such that $n^{2^{-L}} \le 2$. (There's nothing special about the number 2 here; any constant larger than 1 will do.) We have $$n^{2^{-L}} \le 2 \iff 2^{-L}\log n \le 1 \iff \log n \le 2^L \iff L \le \log\log n.$$

• We conclude that $f(n) = \Theta(\log n \log \log n)$.

• +1 for this alternative solution, although I am not familiar with this recursion tree technique.
– favq
Jul 15, 2012 at 15:41

As

$$f\left(2^{\log_2 n}\right)= 2f\left(2^{\log_2 \sqrt{n}}\right)+\log_2 n$$

we can recast this recurrence as

$$r(z)=2r\left(\frac z2\right)+z$$

with $$z=\log_2 n$$ with solution

$$r(z) = C_0 z+z\log_2 z$$

and going backwards

$$f(n) =\left(C_0+\log_2(\log_2n)\right)\log_2n$$

NOTE

$$r(z)=2r\left(\frac z2\right)+z$$

can be recast as

$$s(m)=2s(m-1)+2^m$$

with solution

$$s(m) = (m + C_1)2^m$$