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

Let us assume \(T(n) \le cn^2\) for all \(n \ge n_0\), where \(c\) and \(n_0\) are positive constants. We’ll specify the constants later based on our induction requirements.

Hence, \(T(n - 1) \leq c(n - 1)^2\)

Therefore, we can write:

\[\begin {aligned} T(n) & \le c(n - 1)^2 + n \\ & = cn^2 - 2cn + c + n \\ & = cn^2 - (n(2c - 1) - c) \\ & \le cn^2 \end {aligned}\]The last step holds as long as \((n(2c - 1) - c) \ge 0\). We can use this to specify \(c\) and \(n_0\).

If we pick \(c = 1\), then we need \(n - 1 \ge 0\). Which is possible as long as \(n \ge 1 = n_0\).

#### Solving Without Substitution

This particular problem can be solved using a much simpler method, that does not use substitution.

We can safely assume \(T(0) = k\), where \(k\) is positive constant, as for input size zero we need to do only a constant amount of work, e.g. checking input size and returning.

Therefore:

\[\begin{aligned} T(1) &= T(0) + 1 = k + 1 \\ T(2) &= T(1) + 2 = k + 1 + 2 \\ T(3) &= T(2) + 3 = k + 1 + 2 + 3 \\ \cdots \\ T(n) &= T(n - 1) + n = k + 1 + 2 + 3 + \cdots + n \\ &= k + \frac {n(n + 1)} 2 \\ &= \Theta(n^2) \end{aligned}\]