1 votes 1 votes $T(n)= \begin{Bmatrix} 2^{n}T(n-1)+c& n>0\\ 1 & n=0 \end{Bmatrix}$ Algorithms time-complexity algorithms + – pC asked Jan 23, 2017 reopened Jan 23, 2017 by pC pC 548 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply pC commented Jan 23, 2017 reply Follow Share @prajwal_bhat , i think this recurrence is little bit different and I also need the solution not just time complexity. 1 votes 1 votes Lucky sunda commented Jan 23, 2017 i edited by Lucky sunda Jan 23, 2017 reply Follow Share By substitution method , T(n)=2nT(n−1)+c T(n)=2n2n-1T(n−2)+2nc+c. T(n)=2n2n-12n-2T(n−3)+(2n2n-1c)+(2nc)+c .. .. T(n)=2n2n-12n-2....1 +((2n2n-12n-2....1 )+......+2n2n-1+2n+1)*c {2n2n-12n-2....=2n(n+1)/2} O(2n(n+1)/2 +(2n(n+1)/2+......+2n2n-1+2n+1)c) The series with constant is not GP. I don't know to solve it further. 1 votes 1 votes pC commented Jan 23, 2017 reply Follow Share I need both solution and complexity . Could you plz explain in detail ? 0 votes 0 votes Prajwal Bhat commented Jan 23, 2017 reply Follow Share @pC no problem, Even i didn't see constant part here! 0 votes 0 votes Kantikumar commented Jan 23, 2017 reply Follow Share @pC Is T(n) = 2$\frac{n(n+1)}{2}$ + [ 2$\frac{n(n+1)}{2}$ - 2n ]c answer? 0 votes 0 votes Lucky sunda commented Jan 23, 2017 reply Follow Share I did edit the answer. See it. 0 votes 0 votes Kantikumar commented Jan 23, 2017 reply Follow Share I got the same. After solving (2n(n+1)/2+......+2n2n-1+2n+1) this part, we get [ 2n(n+1)/2 - 2n ]. 0 votes 0 votes Lucky sunda commented Jan 23, 2017 reply Follow Share But how did you solve it?? 0 votes 0 votes Kantikumar commented Jan 23, 2017 reply Follow Share Multiply and divide each term such that you can take 2n(n+1)/2 as common, then you will get GP. Solve it and you will get that. 0 votes 0 votes pC commented Jan 23, 2017 i edited by pC Jan 24, 2017 reply Follow Share 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 1 votes 1 votes Lucky sunda commented Jan 23, 2017 reply Follow Share Ok..I will try it. :) 0 votes 0 votes Please log in or register to add a comment.