Looking at the example on this page, I see that we can solve the recurrence relation
T(n) = T(n-1) + O(n)
like this:
T(n) = T(n-1) + O(n)
= (T(n-2) + O(n-1)) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
...
= T(1) + O(2) + ... + O(n-1) + O(n)
= O(1 + 2 + ... + n-1 + n)
= O(n^2)
This makes pretty good sense until
= O(1 + 2 + ... + n-1 + n) = O(n^2)
Why would it be O(n^2)?