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.