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.

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.