Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$

Question

Hello and thanks for taking the time to answer my question.

The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I prove that this is correct?

I would really appreciate your reasoning behind the concepts as opposed to just churning out a solution.

Thank you very much!

Answer 1

The most basic method is to expand the formula. It rarely works, but it is simple enough that is worth checking before proceeding to more complicated stuff.

\begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) + n \\ &= T(0) + \frac{n(n+1)}{2} = O(n^2) \end{align}

Cheers!

EDIT: Added missing $T(0) = O(1)$ term (thanks to Hurkyl).