What will be the time complexity of recurrence relation T(n)=2T(n-1)+c using substitution method?

Question

Where c is constant.

Answer 1

I am getting $\Theta$ (2^n) .

Comments

You should use $\Theta$ though $O$ is not wrong here :)

---

Done.

---

Very nicely explained. Thanks for the answer. :)

---

Sir ,how to get the intution while solving a recurrence whether we should use theta or Big-O ?And why  here theta is more appropriate ?

---

Unless we approximate we always get $\Theta$. Theta says = while O says <=. So, Theta is more appropriate if it can be used.

---

But theta(n) is used when T(n) =Omega(n) as well as O(n) , so seeing the above solution how to conclude that both of them are asymptotically same .

---

Here, it is other way. In the proof all statements were "=". So, finally we can say it is $\Theta(2^n)$ and hence $O(2^n)$ and $\Omega(2^n)$.