Question

T.C of T(n)=2T(n-1)+n,n > 1 ,T(1)=1 ?

Comments

2^n is a correct answer .

Using substract and conquer method u get O(n2^n) which is correct as

As O(2^n) < O(n2^n)

We can say S&C is giving Worst Case conplexity

Like Quick Sort have O(nlogn) normally & O(n^2) for special case i.e ascending and decreasing sequence..

Can anyone find special case like this for given algo.

---

Will this subtract and conquer method gives upper bound or tight bound ?

Because with subtract and conquer we get O(n2^n)

and when we solve we get O(2^n)

Answer 1

$T(n) = 2T(n-1)+n \\= 2^2T(n-2) + 2(n-1) + n \\=2^3T(n-3) + 2^2(n-2) + 2(n-1) + n \\ .\\. \\.\\=2^{n-1}T(n-(n-1)) + 2^{n-2}(n-(n-2)) + 2^{n-3}(n-(n-3)) + \dots + 2(n-1) + n \\=  2^{n-1}T(1) +  2^{n-2} .2 + 2^{n-3}.3 + \dots + 2(n-1) + n$ $\to (1)$

Now multiply $T(n)$ By 2

$2T(n)=2^n+ 2^{n-1}.2 + 2^{n-2}.3+\dots + 2^2(n-1) + 2n$ $\to (2)$

Now $(2) - (1) \implies \\T(n) =2^n+ 2^{n-1}+ 2^{n-2}+ 2^{n-3}+ \dots +2^2+ 2 -n \\= 2^n +2^{n-1}+ 2^{n-2}+ 2^{n-3}+\dots +2^2+2 -n \\= 2.\frac{(2^{n} -1)}{(2-1)} \text{ (Sum to n terms of GP with a = r = 2) }  -n \\=2^{n+1} -2 - n \\= \Theta\left(2^n\right)$

---

Alternatively,

$T(1) = 1$
$T(2) = 2.1 + 2 = 4$
$T(3) = 2.4 + 3 = 11$
$T(4) = 2.11 + 4 = 26$
$T(5) = 2.26 + 5 = 57$
$T(6) = 2.57 + 6 = 120$
$\dots$ 
$T(n) = 2^{n+1} - (n+2)$

Comments

what mistake i have done? can you point me !

---

yes...why subtract and conquer method get fail here ...???

---

Narasimha Karumanchi's book is not a standard reference. People seem to be getting misled by following it.

Answer 2

Answer is $\theta(2^n)$

Comments

When you are subtracting eq7 with eq6, how are you getting - n in the result, shouldn't it be +n? @Prince Sindhiya

Answer 3

1. This is d correct approach

Comments

they are asymptotically equal.

---

O(n2ⁿ) and O(2ⁿ) are not asymptotically equal.

https://en.wikipedia.org/wiki/Asymptotic_analysis

https://www.encyclopediaofmath.org/index.php/Asymptotic_equality

https://artofproblemsolving.com/wiki/index.php?title=Asymptotic_equivalence

---

k should be zero.then we get correct result