I am trying to solve this recursive relation using the recursion tree method: $T(n) = 2T(n - 1) + \Theta(n)$ with $T(0) = \Theta(1)$.

The answer is $T(n) = 2^n*{\rm constant}_2 + (2^n - 1)n + \Theta(1) = \Theta(n 2^n)$

However, for this question when I sum all the left over terms from the last level to the first, as we do in the recursion tree method, I get $n * \Theta (n)$. I don't get the $\Theta(n * 2^n)$ term anywhere.

Please see my solution below to see how I tried to solve this question. I really want to know where I went wrong...

enter image description here

  • $\begingroup$ Does $\Theta$ stand for a specific function? Or is just just an input of the problem? $\endgroup$ – Charles Jan 31 '12 at 19:51
  • $\begingroup$ its a Landau symbol en.wikipedia.org/wiki/… $\endgroup$ – rrazd Jan 31 '12 at 20:03
  • $\begingroup$ OK, that's what I was suspecting, but I'm not really used to use arithmetic operations over complexity notations. So, if I understand correctly, that means T(n) is equal to 2T(n-1) plus some function in $\Theta(n)$? $\endgroup$ – Charles Jan 31 '12 at 20:09
  • $\begingroup$ yes. The problem is in the context of run time analysis of a divide and conquer algorithm $\endgroup$ – rrazd Jan 31 '12 at 20:15
  • $\begingroup$ Sorry, I can't help much, but what I can say, following your picture, is that I'm not sure how you arrive to your result. Technically, you should have $T(n) = \Theta(n) + 2 * \Theta(n-1) + \cdots = \sum^n_{i=1} 2^i \Theta(n-i)$. You might need to use the fact that $\sum^n_{i=1} 2^i = 2^{n+1} - 1$, but I'm not sure how to solve that exactly. $\endgroup$ – Charles Jan 31 '12 at 20:24

$\Theta(n2^n)$ can’t be correct. Let’s take a look at what happens without the asymptotics, say with $T(n)=2T(n-1)+n$ and $T(0)=1$. Then

$$\begin{align*} T(n)&=2T(n-1)+n\\ &=4T(n-2)+2(n-1)+n\\ &=8T(n-3)+4(n-2)+2(n-1)+n\\ &\,\vdots\\ &=2^kT(n-k)+\sum_{i=0}^{k-1}2^i(n-i)\\ &\,\vdots\\ &=2^nT(0)+\sum_{i=0}^{n-1}2^i(n-i)\\ &=2^n+n(2^n-1)-\sum_{i=0}^{n-1}i2^i\\ &=2^n+n(2^n-1)-\sum_{i=1}^{n-1}\sum_{j=1}^i2^i\\ &=2^n+n(2^n-1)-\sum_{j=1}^{n-1}\sum_{i=j}^{n-1}2^i\\ &=2^n+n(2^n-1)-\sum_{j=1}^{n-1}(2^n-2^j)\\ &=2^n+n(2^n-1)-n2^n+\sum_{j=1}^{n-1}2^j\\ &=2^n-n+2^n-2\\ &=2^{n+1}-n-2\;. \end{align*}$$

This is $\Theta(2^n)$, but it’s not $\Theta(n2^n)$, because it’s not $\Omega(n2^n)$: $$\lim_{n\to\infty}\frac{2^{n+1}-n-2}{n2^n}=0\;.$$


Recall that $\Theta(n)$ denotes any sequence $(R(n))$ such that there exists some finite and positive $n_0$, $c$ and $C$, such that $cn\leqslant R(n)\leqslant Cn$ for every $n\geqslant n_0$. Hence the hypothesis is that, for every $n\geqslant n_0$, $$ 2T(n-1)+cn\leqslant T(n)\leqslant 2T(n-1)+Cn. $$ Equivalently, $t(n)=2^{-n}T(n)$ is such that, for every $n\geqslant n_0$, $$ t(n-1)+cn2^{-n}\leqslant t(n)\leqslant t(n-1)+Cn2^{-n}. $$ Iterating this yields $$ t(n_0)+cs(n)\leqslant t(n)\leqslant t(n_0)+Cs(n),\qquad s(n)=\sum_{k=n_0+1}^{n}k2^{-k}. $$ In particular, for every $n\geqslant n_0+1$, $$ t(n_0)+cs_*\leqslant t(n)\leqslant t(n_0)+Cs^*,\qquad s_*=(n_0+1)2^{-n_0},\quad s^*=\sum_{k=n_0+1}^{+\infty}k2^{-k}. $$ Assume for a moment that $s^*$ is finite. Then $a2^n\le T(n)\leqslant A2^n$ for every $n\geqslant n_0+1$, with $a=t(n_0)+cs_*$ and $A=t(n_0)+Cs^*$, both positive and finite, hence $\color{red}{T(n)=\Theta(2^n)}$.

Finally, $s^*$ is finite if and only if $s_0$ is, where $$ s_0=\sum_{k=0}^{+\infty}k2^{-k}. $$ Recall that $s_0=\frac12\sigma'\left(\frac12\right)$ where, for every $|x|\lt1$, $$ \sigma(x)=\sum_{k=0}^{+\infty}x^k=(1-x)^{-1}, $$ hence $\sigma'(x)=(1-x)^{-2}$ and $s_0=2$ is finite.


OK, I've been very confused by this notation, but are you sure that the answer is $\Theta(n\cdot2^n)$?

Your tree analysis is correct: at the first step, you add $\Theta(n)$, at the next one, you add $2 \Theta(n-1)$, at the next one $4\Theta(n-2)$, etc. In other words, at the $i$-th step, you add $2^i \Theta(n-i)$. Because you need to add all the steps, the actual sum is then $$T(n) = \sum_{i=0}^n 2^i \Theta(n-i)$$ Now, since $\Theta(n)$ means "a function doing $n$ steps of computation", you can rewrite $\Theta(n-i)$ as $\Theta(n)-\Theta(i)$. The sum becomes $$ T(n) = \sum_{i=0}^n 2^i \Theta(n) - 2^i\Theta(i) = \sum_{i=0}^n 2^i \Theta(n) - \sum_{i=0}^n 2^i\Theta(i) $$ If we pull $\Theta(n)$ out of the sum, we can use the fact that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$. Moreover, we can use the fact that $\sum_{i=0}^n i\cdot 2^i = 2(n\cdot 2^n - 2^n+1)$. The sum then becomes: $$ T(n) = n*(2^{n+1} - 1) - 2(n\cdot 2^n - 2^n + 1) = -n + 2^{n+1} - 2 $$ So I would conclude that $T(n)= \Theta(2^{n})$.

Actually, according to Wolfram Alpha, we have $t(n) = -n + 3\cdot2^n - 2$.

So either I also made a mistake in the calculation (which is obviously possible), or the answer is indeed $\Theta(2^n)$, as you found yourself.


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.