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?
Best Answer
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)$.