0

I have seen a solution for it but I was confused at the end.

this is the solution by Siddharth Chakravorty

T(n)=2T(n-1)+n -----(1) T(n-1)=2T(n-2)+n-1 ------(2) T(n-2)=2T(n-3)+n-2 ------(3)

Substitute (3) in (2) and then (2) in (1)

T(n-1)=22T(n-3)+2(n-2)+(n-1)

T(n)= 23T(N-3)+22(n-2)+2(n-1)+n

=> T(k)=2kT(n-k) + 2k−1(n-(k-1))+........+20n

Now, since T(1)=1, let n-k=1 => k=n-1

T(n)=2n−1T(1) + 2n−2(2) + 2n−3(3) + 2n−n(n) --------(4)

Multiply Equation (4) with 2

T(n)=2n+2n−1 + 2n−2 + 2n−3+...... + 2n ----------- (5)

Subtract Equation (5) with (4)

T(n)=2n+2n−1+2n−2+2n−3+........+2 -n

Using sum of GP terms, we get :

[ 21(2n-1) - n ]/ (2-1)

= 2n+1 -2 -n

I am stuck at subtraction of 5 and 4 equations. And does it affect the answer if value of n is given(n>=2) or not?? can anyone explain it ??

Javeria Tariq
  • 1

2 Answers2

1

Try to use Mathjax so it will look clearer. Anyways, after your computation you get this result : $$T(n)= 2^kT(n-k)+\sum_{i=0}^{k-1}(n-i)$$ Let's substitute $k=n-1$
$$T(n)=2^{n-1}+\sum_{i=0}^{n-2}(n-i)$$ $$T(n)=2^{n-1}+\sum_{i=0}^{n-2}n -\sum_{i=0}^{n-2}i$$ $$T(n)=2^{n-1}+n(n-1)-\frac{(n-1)(n-2)}{2}=O(2^n)$$ So $T(n)=\Theta(2^n)$

Roach87
  • 696
0

(4): $ T(n)=\hspace{1.6cm} 2^{n-1}+2^{n-2}\cdot 2+2^{n-3}\cdot 3+...+2^{1}\cdot (n-1)+n$

(5): $2\cdot T(n)=2^{n}+2^{n-1}\cdot 2+2^{n-2}\cdot 3+...+2^{2}\cdot (n-1)+2^1\cdot n$

(5)-(4): $T(n)=2^{n}+2^{n-1}+2^{n-2}+...+2^{1}-n = 2^{n+1}-2-n$

For the subtract, you just need to align those according to terms with the same power of 2. e.g. for $2^{n-1}$ terms. It is $2^{n-1}\cdot 2 - 2^{n-1}=2^{n-1}$, etc.

All those three equations apply for all integers $n \geq 2$. n can be given or not, it does not matters.

Abel Wong
  • 1,173