Substitution Method

• The substitution method for solving recurrence relations consists of three steps:

1. Guess the form of the solution.

2. Verify by induction.

3. Solve for constants.

• Let’s take a look at an example. Suppose we want to solve $T(n) = 4T\left( \frac{n}{2} \right) + n$.

We will assume that $T(1) = \Theta(1)$.

1. Let’s guess that $T(n) \in O(n^3)$. We will assume that $T(k) \leq ck^3$ for $k < n$.

2. Now we need to prove that $T(n) \leq cn^3$ by induction.

The base case is $T(n) = \Theta(1)$ for all $n < n_0$ where $n_0$ is a suitable constant.

We’ll now prove the general case.

\begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4c\left( \frac{n}{2} \right)^3 + n \\ &= \left( \frac{c}{2} \right) n^3 + n \\ &= cn^3 - \left( \left( \frac{c}{2} \right) n^3 - n \right) \\ &\leq cn^3 \end{aligned}

Our desired form was $cn^3$, so we tried to put the equation in the form desired – residual: $cn^3 - \left( \left( \frac{c}{2} \right) n^3 - n \right)$. This is certainly less then our desired form $cn^3$ whenever $\left( \frac{c}{2} \right) n^3 - n \geq$ (residual), for example, if $c \geq 2$ and $n \geq 1$.

3. For $1 \leq n < n_0$, we have $T(n) \leq cn^3$ if we pick $c$ large enough.

And so we’ve shown that $T(n) \in O(n^3)$. But we can do better!

• We shall now prove that $T(n) \in O(n^2)$.

1. We’ll assume that $T\left(k \right) \leq ck^2$ for $k < n$.

2. Now we need to prove this by induction. The base case is the same as before.

Now we attempt to prove the inductive hypothesis.

\begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4c\left( \frac{n}{2} \right)^2 + n \\ &= \left( \frac{c}{2} \right) n^2 + n \\ &= cn^2 - \left( - n \right) \end{aligned}

But there is no $c > 0$ such that $cn^2 - \left( - n \right) \leq cn^2$. It seems like we’ve hit a dead end! But we can actually strengthen the inductive hypothesis by subtracting a low-order term.

Our new inductive hypothesis will be $T(k) \leq c_1 k^2 - c_2 k$ for $k < n$.

\begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4 \left (c_1 \left( \frac{n}{2} \right)^2 - c_2 \left( \frac{n}{2} \right) \right) + n \\ &= c_1 n^2 -2c_2 n + n \\ &= c_1 n^2 - c_2 n - \left( c_2 n - n \right) \\ &\leq c_1 n^2 - c_2 n \text{ if } c_2 \geq 1. \end{aligned}

3. We can pick $c_1$ large enough to handle the initial conditions.

• As you can see, an important part of the substitution method involves making a good guess. But unfortunately, there is no general way to guess the correct solutions to recurrences. If a recurrence is similar to one you’ve seen before, then guessing a similar solution is reasonable.