I want to know, why this is O(n2) for 1+2+3+...+n?
For example, 1+2+3+4 = 4·(4+1)/2 = 10 but 42=16, so how come it's O(n2)?
See Question&Answers more detail:osI want to know, why this is O(n2) for 1+2+3+...+n?
For example, 1+2+3+4 = 4·(4+1)/2 = 10 but 42=16, so how come it's O(n2)?
See Question&Answers more detail:osIn Big-O notation you forget about constant factors.
In your example S(n) = 1+2+...+n = n·(n+1)/2 is in O(n2) since you can find a constant number c with
S(n) < c · n2 for all n > n0
(just choose c = 1).
Notice: Big-O notation is an upper bound, i.e. S(n) grows not faster than n2.
Notice also, that S(n) also grows obviously not faster than n3 so it is also in O(n3).
Some additional:
You can also proof the other way around that n2 is in O(S(n)).
n2 < c·S(n) = c·n·(n+1)/2 holds for any c ≥ 2 for all n
So n2 is in O(S(n)). This means both functions grow asymtoticly equal. You can wirt this as S(n) is in Θ(n2).