I have the following recurrence relation:


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$?


  • $\begingroup$ it looks ok to me, but i'd recommend proving $T_(n)=2^n T(0)$ using induction in $n$ - but in the end the 'best way to prove something' is a matter of taste $\endgroup$
    – supinf
    Commented May 17, 2015 at 10:36
  • $\begingroup$ I would say that what you have done is discover that $T(n)=2^nT(0)$ for non-negative integer $n$. To prove it, I would reverse your argument as an easy induction (rather like people who try to start the a proof of a statement with that statement and end up with $0=0$ when in fact their attempted proof is back-to-front and easily reversible). $\endgroup$
    – Henry
    Commented May 17, 2015 at 10:39
  • $\begingroup$ So you mean that for a positive n, the algorithm is in $O(n^2)$ ? $\endgroup$ Commented May 17, 2015 at 10:41


You must log in to answer this question.

Browse other questions tagged .