[Math] Solving recurrence relation $T(n) = 2T(n – 1) + \Theta(n)$ using the recursion tree method

recurrence-relationsrecursive algorithms

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

Best Answer

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

Related Question