Why does O(1 + 2 + ... + n-1 + n) = O(n^2)?

72 Views Asked by At

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)?