solve recurrence by substitution

To solve for an upper bound of a recurrence via substitution:

1. Guess the form of the solution (e.g. $T(n)\approx n^2$).
2. Verify by induction. Use strong induction if there are lower order terms.
3. Solve for constant coefficients.

Simple Case

For instance, we might have the recurrence $T(n)$:

$$T(n)=2T\left(\frac{n}{2}\right)+n^2$$

Alternatively, we can write this as (i.e. $n^2$ can have any constants or lower order terms; the upper bound will not change):

$$T(n)=2T\left(\frac{n}{2}\right)+O(n^2)$$

A closed-form upper-bound for $T(n)$, i.e. $O(g(n))$, we need to find $c$ and $n_0$ such that:

$$T(n)\le c\cdot g(n),n\ge n_0$$

We can first guess that $T(n)=O(n^2)$, i.e. $T(n)\le c\cdot n^2$ for $n>n_0$ and verify it as so:

$$\begin{array}{rlr}T(n)& =2T\left(\frac{n}{2}\right)+n^2& \\ & \le 2c{\left(\frac{n}{2}\right)}^2+n^2& \le c\cdot n^2\\ & \le \frac{c\cdot n^2}{2}+n^2& \le c\cdot n^2\end{array}$$

Then, solve for $c$:

$$\begin{array}{rl}\frac{c}{2}+1& \le c\\ 1& \le \frac{c}{2}\\ 2& \le c\end{array}$$

Dealing with lower-order terms

The above strategy takes a bit more work if lower-order terms are involved. For instance, say we have $T(n)$ defined below:

$$T(n)=4T\left(\frac{n}{2}\right)+n$$

We might guess that $T(n)$ is approximately $O(n^2)$, but it is be harder to prove directly, since there is also a lower-order $n$ term, which cannot share the same $c$. Instead, we can add another constant for $n$ in the induction hypothesis by subtracting a lower-order term:

$$T(k)\le c_1{k}^2-c_{2}k,k<n$$

Now we can verify the guess as so:

$$\begin{array}{rl}T(n)& =4T\left(\frac{n}{2}\right)+n\\ & =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-(c_{2}n-n)\\ & \le c_1{n}^2-c_{2}n,c_2{\ge }_1\\ & \le c_1{n}^2\\ T(n)& =O(n^2)\end{array}$$