# 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.

• Does it help to simplify $4^{\lg\lg n}$ as $(\lg n)^2$? – alex.jordan Nov 21 '12 at 2:16
• Can you explain "For each recursion we will have 4 new branches" to me? I don't understand this, but I have little to no experience with computational complexity. – alex.jordan Nov 21 '12 at 2:18
• The first call of T(n) will generate 4 branches, each one of this branches will call 4 new branches and so on – dreamcrash Nov 21 '12 at 2:26
• That's what I don't understand. If I call $T(16)$, then what I see in your recursion makes me call $T(4)$, and that's it. I'm only seeing "one branch" as opposed to a recursion like $T(n)=T(\sqrt{n})+T(n/4)$, where I would see one call as branching into two. – alex.jordan Nov 21 '12 at 3:07
• You are right. I just edit. – dreamcrash Nov 21 '12 at 14:55

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)$.

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)$.