Show that the solution of \(T(n) = T(n-1) + n\) is \(O(n^2)\).

In order to use the substitution method, we guess that the solution is \(O(n^2)\) and must prove that \(T(n) \leq cn^2\) for some \(c > 0\). We assume that this bound holds for all positive \(m < n\) such as \(m = n - 1\):

\[T(n - 1) \leq c(n-1)^2\]

Substituting into the recurrence yields

\[\begin{split} T(n) & \leq c(n-1)^2 + n \\ & = cn^2 -2cn + n + c \ \ \ ( \text{let} \ c = 1 ) \\ & = n^2 -2n + n + 1 \\ & = n^2 -n + 1 \\ & \leq n^2 \\ \end{split}\]

We say that the last step holds for \(n \geq 1\) and \(c = 1\) as noted above. To be clear, the last step is claiming \(n^2 -n + 1 \leq n^2 \ \forall \ n \geq 1\) which wasn’t immediately clear to me with this notation for the substitution method.