Substitution method

The substitution method applies induction to find the asymptotic bounds for a given recurrence. It comprises two main steps:

• We guess the form of the solution using symbolic constants (inductive hypothesis).
• Use induction to show that the solution works (inductive step), then find the constants.

Process

Given a particular recurrence $T(n)$, we make a guess for its running time. It’s better to prove big-O and big-Ω separately before proving big-Θ.

For example, say we assume $T(n)\in O(n\lg n)$, for $T(n)=2T(\lfloor n/2\rfloor )+\Theta (n)$.

• We adopt the inductive hypothesis that $T(n)\le cn\lg n$, for all $n\ge n_0$.
• Assume by induction that this bound holds for all numbers at least as big as $n_0$ and less than $n$. Therefore:
  • If $n\ge 2n_0$, it holds for at least $\lfloor n/2\rfloor$.
• This yields $T(\lfloor n/2\rfloor )\le \lfloor n/2\rfloor \lg (\lfloor n/2\rfloor )$.
• We substitute this into the recurrence, which yields: $T(n)\le cn\lg n$, as required.
• Then, we have to define $n_0$ and $c$, which shouldn’t be too difficult.
• Then, we prove the base case. We perhaps ought to define the lowest recursive term manually, so that we don’t accidentally go too far or suggest a term takes $0$ time, because this can never happen (CPU cycles).