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