math - Big O notation O(n²)

Question

I want to know, why this is O(n²) for 1+2+3+...+n?

For example, 1+2+3+4 = 4·(4+1)/2 = 10 but 4²=16, so how come it's O(n²)?

Answer 1

In Big-O notation you forget about constant factors.

In your example S(n) = 1+2+...+n = n·(n+1)/2 is in O(n²) since you can find a constant number c with

S(n) < c · n² for all n > n₀

(just choose c = 1).
Notice: Big-O notation is an upper bound, i.e. S(n) grows not faster than n².
Notice also, that S(n) also grows obviously not faster than n³ so it is also in O(n³).

Some additional:

You can also proof the other way around that n² is in O(S(n)).

n² < c·S(n) = c·n·(n+1)/2 holds for any c &geq; 2 for all n

So n² is in O(S(n)). This means both functions grow asymtoticly equal. You can wirt this as S(n) is in Θ(n²).