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

Question

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?

Answer 1

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)$.

Answer 2

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 $$