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}