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.
Best Answer
For every $k\geqslant0$, let $U(k)=T(2^k)$, then $U(k)=4U(k/2)+2^k$ hence $U(k)\geqslant2^k$ for every $k$.
Choose $C\geqslant2$ so large that $U(k)\leqslant C 2^k$ for every $k\leqslant5$. Let $k\geqslant6$. If $U(k-1)\leqslant C2^{k-1}$, then $U(k)\leqslant 4C2^{k/2}+2^k$. Since $k\geqslant3$, $2^{k/2}\leqslant 2^k/8$ hence $U(k)\leqslant (C/2+1)2^k$. Since $C/2+1\leqslant C$, the recursion is complete.
Finally, $U(k)=\Theta(2^k)$.