2
$\begingroup$

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.

  • 0
    Does it help to simplify $4^{\lg\lg n}$ as $(\lg n)^2$?2012-11-21
  • 0
    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.2012-11-21
  • 0
    The first call of T(n) will generate 4 branches, each one of this branches will call 4 new branches and so on2012-11-21
  • 0
    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.2012-11-21
  • 0
    You are right. I just edit.2012-11-21
  • 0
    @dreamcrash: Please, check if I make everything correct in LaTeX.2012-11-21
  • 0
    @m0nhawk Yes it is thanks :)2012-11-21
  • 0
    The exponent of 4 should be just $i$, not $i+1$.2012-11-21
  • 0
    You are right the first level don't have 4 branches2012-11-21
  • 0
    @ZachLangley do you think it is possible to simplify into something like x^i ?2012-11-21
  • 0
    @dreamcrash Are you looking for an exact solution or just the asymptotic growth (Big-Oh notation)?2012-11-21
  • 0
    @ZachLangley An asymptotic growth (Big-Oh notation)2012-11-21
  • 0
    It looks like $T(n) = O(n)$. (Look at the last term in the summation.)2012-11-21
  • 0
    Yep it looks something like kn, indeed.2012-11-21
  • 0
    @dreamcrash: I see no LaTeX there. What's wrong?2012-11-21
  • 0
    $$ 4^{i} n^{0.5^i}$$ can be simplify to $$ (4n^{0.5})^{i}$$ Sorry, i didn't know how to used it.2012-11-21
  • 0
    @dreamcrash No. $(n^{0.5})^i = n^{0.5i} \ne n^{{0.5}^i}.$2012-11-21
  • 0
    @ZachLangley Thanks a lot for you help.2012-11-21

2 Answers 2

1

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

1

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