Using the master method in Section 4.5, you can show that the solution to the recurrence $$T(n) = 4T(n/2) + n$$ is $$T(n) = \Theta(n^2)$$. Show that a substitution proof with the assumption $$T(n) \le cn^2$$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Let us assume $$T(n) \le cn^2$$ for all $$n \ge n_0$$, where $$c$$ and $$n_0$$ are positive constants.

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

With this we cannot prove our assumption in it’s exact form.

Now, let us assume $$T(n) \le cn^2 - bn$$ for all $$n \ge n_0$$, where $$b$$, $$c$$, and $$n_0$$ are positive constants.

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

The last step holds as long as $$(b - 1)n$$ is positive.

If we set $$n_0 = 1$$, our hypothesis works for any $$b \ge 1$$.

Note: We have just shown the $$O$$-bound. But to show $$\Theta$$-bound, we also need to show $$\Omega$$-bound, which can be done by adding the lower order term instead of subtracting.