Substitution method

This one relies on a good guess but it will show that it is a good guess

  1. guess the correct runtime T(n)T(n)
  1. prove it through induction, and get any parameters like cc you need
  1. re-do the inductive proof with these parameters

To be more specific, we hypothesize that T(n)cf(n)T(n) \leq cf(n), and then we plug this into the recurrence relationship. For example, if we wanted to show that T(n)=T(n3)+nT(n) = T(n-3) + n is O(n2)O(n^2), we would plug in

c(n3)2+ncnc(n-3)^2 + n \leq cn

and you would get something like

cn6n9c \geq \frac{n}{6n - 9}

and this has a constant upper bound.

Guessing correctly

The major mode of guessing is rolling out the recurrence relationship, like what is shown below

There’s a pretty straightforward strategy

  1. expand (unfold the recurrence like an onion)
  1. simplify (group like terms)
  1. notice the pattern. The best way is to look at things in terms of depth tt, and then you know what tt is (typically a logarithm). Watch out for edge cases. To check, plug in the starting depth to the formula to see if you get the original recurrence relationshp

Alternatively, you can also guess by graphing, etc.


This is a simple case of induction and it’s very similar to how you show normal complexity. You want to show that T(n)cf(n)T(n) \leq c f(n) when nn0n \geq n_0. The best way to attempt this is through strong induction. Write out the recurrence relation, and then for each recurrent term, plug in your inductive hypothesis (namely that T(n)cf(n)T(n) \leq c f(n).

At this point, you will have an equation in terms of nn and cc. Try solving for cc, or a bound of it.

If you made an incorrect assumption, you will get some bound like c<0c < 0, which is a contradiction. If you have made a correct complexity assumption, then you will get some bound of cc that is valid.

If you’re made it this far, you are to plug this cc back into the original equation and show again by induction that the assumptions are satisfied for some value of n>n0n > n_0.

Things to watch out for

It can happen that the substitution method fails a complexity estimate when it is asymptotically correct.

You also can’t do induction on general O(f(n))O(f(n)), because that would mean assigning some cc to every value of nn, which is not correct. Instead, you should pick the largest term and work with lower bounds f(n)cg(n)f(n) \leq c g(n) where g(n)g(n) is simple