Alo doubt

Question

Complexity of equation -

T(n)=.    2T(n-1)-1   if n>0

              1.                 Otherwise

Comments

O(1) .

---

Right ....Can give detail explanation...

---

T(0) = 1
T(1) = 2T(0) - 1 = 1
T(2) = 2T(1) - 1 = 1
T(3) = 2T(2) - 1 = 1
...
T(i) = 1
Therefore, T does not depend on the input n. It is always 1 (constant).
Hence complexity is O(1)

---

Thanku @rishabh gupta

Answer 1

Edited! Sorry that was some dumb mistake @suraj

Comments

@abhijit  procedure is right but at last u have written wrong

Answer is O(1)

Answer 2

T(n)=2T(n-1) - 1, n>0

T(0)=1

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

T(n)=2(2(T(n-2)-1)-1  = 2²T(n-2)-3        // T(n-1)=2T(n-2)-1                                  

T(n)=2(2(2T(n-3)-1))-3 = 2³T(n-3)-7                                         //  T(n-2)=2T(n-3)-1                         

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

When n=k

T(n)=2ⁿT(0)-(2ⁿ-1)= 2ⁿ-2ⁿ⁺1=1=O(1)