Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.