Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

Question

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with $O(2^n)$ or $\Theta(2^n)$ as answer (as I would have said).

Does any one knows why is only $\Omega(2^n)$?

Answer 1

$T(n)=2T(n-1) + c $, c is a constant

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

Replacing value of $T(n-1)$ in first equation we get, $T(n)=2(2T(n-2) +c)+c =2^2T(n-2)+2c+c$

In the same way by replacing value of $T(n-2)$ we get, $T(n)=2^2(2T(n-3)+c)+2c+c=2^3T(n-3)+2^2c+2c+c$

In general, $T(n)=2^kT(n-k)+2^{k-1}c+2^{k-2}c+\ldots+2c+c$, where $1 \leq k\leq n-1$

In base case say, $T(1)=c'$ a constant. Then considering $k=n-1$, $T(n)=2^{n-1}T(1)+2^{n-2}c+2^{n-3}c+\ldots+2c+c=\Theta(2^n).$

This implies, $T(n)=O(2^n)$ and $T(n)=\Omega(2^n)$

In general this way of solving recurrences is called Expansion method.