find the time complexity|testbook livetest

Question

please tell the time complexity?i was getting O(2n)

Comments

by repeted sustitution we gte T(n-1) = 2^n-1T(n-2)

so T(n) = 2^n . 2^n-1T(n-2)

so y doin this we can get a pttran as T(n) = 2^(n + n-1 + n-2 +n-3..........1)T(0);

2^(n*n+1)/2

which can be written as $^{\sqrt{2}}$^(n*(n+1))

so that's the answer.

---

yes..it was a calculation mistake:-(

i got those power terms as sum.

---

you won't repeat the mistake now.. :)

Answer 1

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

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

Similarly, T(n-k) = 2^n-kT(n-k-1)

So, T(n) = 2ⁿ(2^n-1(2^n-2..............2^n-kT(n-k-1)))

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

Let, n-k-1=0

So, k=n-1

$\therefore$ T(n) = 2^{n+(n-1)+(n-2)+......+1}T(1) [Substituting k with n-1]

= T(n) = $2^{\frac{n(n+1)}{2}}$ = $\sqrt{2}^{n^{2}+n}$

This is how I did in the test.

Comments

@Debashish_Deka,  This $T(n)$ should be $2^n T(n-1)+c$ , right ? Why not considering the constant part here ?

---

yes... for time complexity I think constant part should be there, and considering that ,

T(n) = $\sum _{k=0}^{n} \left ( \sqrt{2} \right )^{2kn-k^2+k}$. I have not calculated that, But answer I think will not change. Same case with $T(n) = 2*T(n/2) + O(1) $ ...answer comes out to be linear in both ways.

---

..........................