Prove $T(n) = 2T(n-1) \in \Theta(2^n)$

Question

Not sure how to prove this since there's no cost associated with each recursion.

Answer 1

You can always just find a closed-form solution, especially when the recurrence is this simple. Observing that $T(0) = c, T(1) = 2c, T(2)=4c, \cdots,$ we can see that $T(n) = c \cdot 2^n$, for some constant $c$, and thus, this relation grows with $2^n$, i.e. it is $\Theta(2^n)$.