Solving recurrence relation $T(n) = 2T(n - 1) + \Theta(n)$ using the recursion tree method

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

-
Does $\Theta$ stand for a specific function? Or is just just an input of the problem? –  userxxxxx Jan 31 '12 at 19:51
its a Landau symbol en.wikipedia.org/wiki/… –  rrazd Jan 31 '12 at 20:03
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)$? –  userxxxxx Jan 31 '12 at 20:09
yes. The problem is in the context of run time analysis of a divide and conquer algorithm –  rrazd Jan 31 '12 at 20:15
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. –  userxxxxx 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.

-