I was trying to solve this recurrence $T(n) = 4T(\sqrt{n}) + n$. Here $n$ is a power of $2$.
I had try to solve like this:
So the question now is how deep the recursion tree is. Well, that is the number of times that you can take the square root of n before n gets sufficiently small (say, less than $2$). If we write: $n = 2^{\lg(n)}$ then on each recursive call $n$ will have it's square root taken. This is equivalent to halving the above exponent, so after $k$ iterations we have: $n^{1/2^{k}} = 2^{\lg(n)/2^{k}}$ We want to stop when this is less than $2$, giving:
\begin{align} 2^{\lg(n)/2^{k}} & = 2 \\ \frac{\lg(n)}{2^{k}} & = 1 \\ \lg(n) & = 2^{k} \\ \lg\lg(n) & = k \end{align} So after $\lg\lg(n)$ iterations of square rooting the recursion stops. For each recursion we will have $4$ new branches, the total of branches is $4^\text{(depth of the tree)}$ therefore $4^{\lg\lg(n)}$. And, since at each level the recursion does $O(n)$ work, the total runtime is: \begin{equation} T(n) = 4^{\lg\lg(n)}\cdot n\cdot\lg\lg(n) \end{equation}
But appears that this is not the correct answer...
Edit:
$T(n) = \sum\limits_{i=0}^{\lg\lg(n) - 1} 4^{i} n^{1/2^{i}}$
I don't know how to get futher than the expression above.