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


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

  • $\begingroup$ Does it help to simplify $4^{\lg\lg n}$ as $(\lg n)^2$? $\endgroup$ – alex.jordan Nov 21 '12 at 2:16
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Nov 21 '12 at 2:18
  • $\begingroup$ The first call of T(n) will generate 4 branches, each one of this branches will call 4 new branches and so on $\endgroup$ – dreamcrash Nov 21 '12 at 2:26
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Nov 21 '12 at 3:07
  • $\begingroup$ You are right. I just edit. $\endgroup$ – 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)$.

| cite | improve this answer | |

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.