#self doubt

Question

how to solve this? 

Comments

@samarpita

 

---

$T(n) = 2^n T(n-1) + c$

$T(n)= 2^n[2^{n-1}T(n-2)+c] + c= 2^{n+(n-1)}T(n-2) + 2^nc + c$

$T(n)= 2^{n+(n-1)}[ 2^{n-2}T(n-3) +c ] + 2^nc + c = 2^{n+(n-1)+(n-2)}T(n-3) + 2^{n+(n-1)}c +  2^n c + c$

$\cdots$

$\cdots$

$T(n) = 2^{n+ (n-1) + (n-2)+….+(n-k+1)}T(n-k)+2^{n+(n-1)+(n-2)+….(n-k+2)}c +….+2^{n+(n-1)}c +  2^n c + c$

Consider $T(1)=1,$ So, $n-k=1 \implies k=n-1$

$T(n)= 2^{n+(n-1)+(n-2)+...+2}\times 1 + 2^{n+(n-1)+(n-2)+...+3}c + …..+2^{n+(n-1)}c +  2^n c + c$

$T(n)= 2^{2+3+...+(n-2)+(n-1)+n} + 2^{3+...+(n-2)+(n-1)+n}c + …..+2^{(n-1)+n}c +  2^n c + c$

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

$T(n)= \frac{2^{\frac{n(n+1)}{2}}}{2} + \frac{2^{\frac{n(n+1)}{2}}c}{2^{1+2}} +….+ \frac{2^{\frac{n(n+1)}{2}}c}{2^{1+2+...+(n-2)}}+ \frac{2^{\frac{n(n+1)}{2}}c}{2^{1+2+...+(n-1)}} + \frac{2^{\frac{n(n+1)}{2}}c}{2^{1+2+...+n}}$

$T(n) = \frac{2^{\frac{n(n+1)}{2}}}{2} + c \times 2^{\frac{n(n+1)}{2}} \left(\frac{1}{2^{1+2}}+...+\frac{1}{2^{1+2+...+(n-1)}} + \frac{1}{2^{1+2+...+n}}\right) $

$T(n) = \frac{2^{\frac{n(n+1)}{2}}}{2}+ c \times 2^{\frac{n(n+1)}{2}} \left (\sum_{k=2}^{n} \left(\frac{1}{2^{\sum_{p=1}^{k}p}}\right)\right)$

With $T(1)=1,$ you can put $n=2,3,4,..$ and check whether this formula of $T(n)$ is correct or not..

---

"blocking user" feature is not available here.. question might be hidden by someone. You can try stackoverflow, cs.stackexchange etc to ask compiler related questions if you are facing issue here..

Answer 1

@samarpita

Let’s expand the recurrence:

Your code lacks the +c part of the recursion,

so I assume that the code is wrong and the recursion T(n) = 2^nT(n-1) + c is correct...

Let f(n)=T(n)/c!,

then f(n)

= T(n)/c!

= n(T(n-1)+1)/c!

= T(n-1)/(n-1)! + 1/(n-1)!

= f(n-1) + 1/(n-1)!

= sum(1,n-1, 1/k!)

~ e

Thus T(n) ~ e*c!…

 

 

1. https://gateoverflow.in/247755/Can-we-solve-the-recurrence-n-by-masters-theorem-if-possible 

 

2. https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture3.pdf

 

3. https://gateoverflow.in/16246/T-n-t-n-2-n-recurrence-equation-solution-t-1-1 

 

4. https://gateoverflow.in/46274/T-n-t-n-1-t-n-2-n