$T(n) = 2T(n-1)$ Recurrences
Note: The original version of the post included the initial values $T(0) = 0$ and $T(1) = 1$.

If $T(n) = 2T(n-1)$ for all $n &gt; C$ then, as you can prove by induction,
$$ T(n) = 2^{n-C} T(C). $$
In particular, in your case $T(n) = 2^{n-1}$. Note that given your initial values, the recurrence $T(n) = 2T(n-1)$ cannot hold for $n=1$; presumably it holds for all larger $n$.

You are asking for the complexity of the recurrence. Recurrences have no such thing as complexity. A recurrence might describe the running time of an algorithm, and then its solution is the time complexity of the algorithm. But a recurrence can describe any number of things, or even be completely abstract.