Asymptotic Notation

Question

Time Complexity of

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

by using substitution method

Comments

T(n)=2T(n)+n=22T(n−2)+2(n−1)+n=23T(n−3)+22(n−2)+2(n−1)+n...=2n−1T(n−(n−1))+2n−2(n−(n−2))+2n−3(n−(n−3))+⋯+2(n−1)+n=2n−1T(1)+2n−2.2+2n−3.3+⋯+2(n−1)+nT(n)=2T(n)+n=22T(n−2)+2(n−1)+n=23T(n−3)+22(n−2)+2(n−1)+n...=2n−1T(n−(n−1))+2n−2(n−(n−2))+2n−3(n−(n−3))+⋯+2(n−1)+n=2n−1T(1)+2n−2.2+2n−3.3+⋯+2(n−1)+n →(1)→(1)

 

Now multiply T(n)T(n) By 2

2T(n)=2n+2n−1.2+2n−2.3+⋯+22(n−1)+2n2T(n)=2n+2n−1.2+2n−2.3+⋯+22(n−1)+2n →(2)→(2)

Now (2)−(1)⟹T(n)=2n+2n−1+2n−2+2n−3+⋯+22+2−n=2n+2n−1+2n−2+2n−3+⋯+22+2−n=2.(2n−1)(2−1) (Sum to n terms of GP with a = r = 2) −n=2n+1−2−n=Θ(2n)(2)−(1)⟹T(n)=2n+2n−1+2n−2+2n−3+⋯+22+2−n=2n+2n−1+2n−2+2n−3+⋯+22+2−n=2.(2n−1)(2−1) (Sum to n terms of GP with a = r = 2) −n=2n+1−2−n=Θ(2n)

Answer 1

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

Proceeding like this we get.
T(n) = 2^k T(n-k) + 2^(k-1) (n - (k - 1)) + ...... 2^2 * (n-2) + 2*(n-1) + n

Now T(1) = 1 so putting k = n - 1 we get.
T(n) = 2^(n-1) * T(1) + 2^(n-2)* (n - (n - 1 - 1)  + ....... 2^2 * (n-2) + 2*(n-1) + n

T(n) = 2^(n-1) * 1 + 2^(n-2) * 2  + 2^(n-3) * 3  + ........ 2^2 * (n-2) + 2*(n-1) + n

T(n) = $\sum (n - k) * 2^k$  = $\sum n * 2^k$  - $\sum k * 2^k$
k is starting from 0 to n - 1.

T(n) = n $\sum 2^k$  - $\sum k * 2^k$
First series is G.P and second series is slightly complicated..
$\sum 2^k$ = 2^n - 1
$\sum k * 2^k$ = ( n - 2 ) * (2 ^n ) + 2. Prove of this given here. 

So T(n) = O ( 2^n)