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

2. prove it through induction, and get any parameters like $c$ you need

3. re-do the inductive proof with these parameters

To be more specific, we hypothesize that $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(n-3) + n$ is $O(n^2)$, we would plug in

and you would get something like

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)

2. simplify (group like terms)

3. notice the pattern. The best way is to look at things in terms of depth $t$, and then you know what $t$ 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.

Proving

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) \leq c f(n)$ when $n \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) \leq c f(n)$.

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

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

If you’re made it this far, you are to plug this $c$ back into the original equation and show again by induction that the assumptions are satisfied for some value of $n > 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))$, because that would mean assigning some $c$ to every value of $n$, which is not correct. Instead, you should pick the largest term and work with lower bounds $f(n) \leq c g(n)$ where $g(n)$ is simple