What is wrong with my solution for the recurrence $T(n)=2T(\sqrt{n})+\lg\lg n$? an someone explain where did I do a mistake?
Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$
Let$$\lg n = m$$
$$S(m) = 2S(m/2)+\lg m$$
We know (proved in class) that $$S(m) = O(m \lg m)$$
Therefore:
$$T(n)= \Theta(\lg n \cdot \lg\lg n)$$
I will be thankful for you help!
 A: This recurrence can be solved completely, which leads to insight as far as why the Theta asymptotic isn't correct.

$$T(n) = 2T(\sqrt n) + \lg \lg n$$

Similar to what you said , let $S(n) = T(2^n)$, so
$$S(n) = 2T(\sqrt{2^n}) + \lg \lg 2^n = 2T(2^{n/2}) + \lg n = 2S(n/2) + \lg n $$
Then do it again, let $R(n) = S(2^n)$:
$$\begin{align}
R(n) &= 2S(2^n ~/~ 2) + \lg( 2^n ) \\
&= 2S(2^{n - 1}) + n \\
 &= 2R(n - 1) + n 
\end{align}$$
which is a recursion that has a general solution 
$$R(n) = 2^n\left(R(0) + 2\right) - 2 - n$$
Now we can back substitute using $S(n)= R(\lg n)$ to find that 
$$S(n) = n\left(S(1) + 2\right) - 2 - \lg n$$
and again to find
$$T(n) = \lg n\left(T(2) + 2\right) - 2 - \lg \lg n$$
Now we can see that the asymptotic behavior is:
$$T \in \Theta\bigg(\lg n\bigg)$$


Can someone explain where did I do a mistake?

If the constants in the recursion had been different, then the $R(n)$ recursion could have had a $n2^n$ term in it: it would have been of the form
$$R(n) = Xn2^n + Y2^n + Zn + W$$
$X \ne 0$ would have added a $(\lg n)(\lg \lg n)$ term in the $T(n)$ solution.
$O()$ asymptotic is an upper bound , $\Theta()$ asymptotic is both an upper and lower bound.
So while it is true that $T \in O((\lg n)(\lg \lg n))$ as your attempt suggested, because of the choice of constants, the $(\lg n)(\lg \lg n)$ term disappears and the $(\lg n)$ term is left to uphold the the growth of $T$, being both an asymptotic upper and lower bound.
A: Your assumption that $$S(m)=2S(m/2)+\lg m$$ yields $$S(m)=O(m \lg m),$$ can be tightened. By the Master Theorem, $S(m) = \Theta(m)$.
See DanielV's answer for the full solution.
