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?
 A: 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)$.
