I have the following recurrence relation:
$$T(n)=2T(n-1)$$
I would like to find the running time of the algorithm. I tried the following, having in mind that the correct solution is $$O(2^n)$$
So here are my calculations $$2T(n-1) = 4T(n-2) = 8T(n-3) = 16T(n-4)$$ $$... = 2^kT(n-k)$$
As you can see, I observe that each time the number before the T(n-1) is always the 2 to the power of k.
From here I can say that:
Let: $n-k = 0$ $\Rightarrow$ $n = k$.
So: $$2^nT(n-n) = 2^nT(0)$$
And therefore the solution is $$O(2^n)$$ I would like to ask, if the way that I solved the recurrence relation is a valid one and it is proving the recurrence relation is in the class of $2$ to the power of $n$?
CHeers