How to solve this recurrence relation: $T(n) = 4\cdot T(\sqrt{n}) + n$ 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. 
 A: 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)$.
A: We want to find a simple upper bound for $$T(n) = \sum_{i=0}^{\lg\lg{n}-1} 4^i n^{1/2^i}.$$
Note that the first summand is $n$ and the last summand is less than 
$$4^{\lg\lg{n}} n^{1/2^{\lg\lg{n}}} = \log^2{n} \cdot n^{1/\lg{n}}.$$
The first term is significantly larger and probably doing most of the work, so we will aim to show that $T(n) = O(n)$.  Indeed,
\begin{align*}
T(n) &= \sum_{i=0}^{\lg\lg{n}-1} 4^i n^{1/2^i}\\
 &\le n + \sum_{i=1}^{\lg\lg{n}} 4^i n^{1/2^i}\\
 &\le n + \sum_{i=1}^{\lg\lg{n}} 4^i \sqrt{n}\\
 &\le n + \sqrt{n}\lg\lg{n} + \sum_{i=1}^{\lg\lg{n}} 4^i\\
 &\le n + \sqrt{n}\lg\lg{n} + \frac{4\lg^2{n} - 1}{4 - 1}\\
 &= O(n).
\end{align*}
Also, clearly $T(n) \ge n$, so we have $T(n) = \Theta(n)$.
