Recurrence Realtion Soution and Time Complexity

Question

$T(n)= \begin{Bmatrix} 2^{n}T(n-1)+c& n>0\\ 1 & n=0 \end{Bmatrix}$

Comments

@prajwal_bhat , i think this recurrence is little bit different and I also need the solution not just time complexity.

---

By substitution method , 

T(n)=2ⁿT(n−1)+c

T(n)=2ⁿ2^n-1T(n−2)+2ⁿc+c.

T(n)=2ⁿ2^n-12^n-2T(n−3)+(2ⁿ2^n-1c)+(2ⁿc)+c

..

..

T(n)=2ⁿ2^n-12^n-2....1 +((2ⁿ2^n-12^n-2....1 )+......+2ⁿ2^n-1+2ⁿ+1)*c

{2ⁿ2^n-12^n-2....=2^n(n+1)/2}

O(2^n(n+1)/2 +(2^n(n+1)/2+......+2ⁿ2^n-1+2ⁿ+1)c)

The series with constant is not GP. I don't know to solve it further.

---

I need both solution and complexity . Could you plz explain in detail ?

---

@pC no problem, Even i didn't see constant part here!

---

@pC Is T(n) = 2^{$\frac{n(n+1)}{2}$} + [ 2^{$\frac{n(n+1)}{2}$} - 2ⁿ ]c answer?

---

I did edit the answer. See it.

---

I got the same. After solving (2^n(n+1)/2+......+2ⁿ2^n-1+2ⁿ+1) this part, we get  [ 2^n(n+1)/2 - 2ⁿ ].

---

But how did you solve it??

---

Multiply and divide each term such that you can take 2^n(n+1)/2 as common, then you will get GP. Solve it and you will get that.

---

Im stuck at here

$\begin{align*} T(n)&= 2^n T(n-1)+c \\ T(n-1)&= 2^{n-1} T(n-2)+c \\ T(n-2)&= 2^{n-2} T(n-3)+c \\ ..\\ ..\\ T(n)&= 2^{n} T(n-1)+c \\ &= 2^{n} [2^{n-1} T(n-2)+c]+c\\ &= 2^{n} 2^{n-1} T(n-2)+2^{n}c+c \\ &= 2^{n} 2^{n-1} [2^{n-2} T(n-3)+c]+2^{n}c+c\\ &= 2^{n} 2^{n-1} 2^{n-2} T(n-3)+ 2^{n} 2^{n-1}c+2^{n}c+c \\ &= 2^{n+(n-1)+(n-2)+..+1} T(n-k) +[ 2^{n+(n-1)+(n-2)+..+1}+2^{n+(n-1)+(n-2)+..+2}+...+2^{n}]c\\ &=2^{\frac{n(n+1)}{2}} ?? \end{align*}$

Now, multiplying and diving to take out common term

$\begin{align*} [ 2^{n+(n-1)+(n-2)+..+1}+2^{n+(n-1)+(n-2)+..+2}+...+2^{n}] \\ =& 2^{n+(n-1)+(n-2)+..+1}[\frac{1}{1}+\frac{1}{1.2}+\frac{1}{3!}...+\frac{1}{(2^{n})!}]\\ =&2^{\frac{n(n+1)}{2}}[\sum_{i=1}^{2^n}\frac{1}{i !}] \end{align*}$

How to proceed further

---

Ok..I will try it. :)