The sum of integers 1..n is \approx \frac{n^2}{2}, which is
Series like this actually come up quite a bit:
1 + 2 + 3 + ... + (n-1) + nOr, equivalently, the other way around:
n + (n-1) + ... + 3 + 2 + 1And sometimes the last n is omitted, but as we'll see it doesn't affect the big O:
(n-1) + (n-2) + ... + 3 + 2 + 1Let's draw this out. Let's say n=10, so we'll represent n-1 as nine circles:
We can continue the pattern with n-2
And n-3, n-4, etc, all the way down to 1:
Notice both the top and right "sides" of our set of circles have n-1 items:
In fact, we could imagine our circles inside of a square with sides of length n-1:
Notice that we've filled in just about half of the square!
Of course, the area of the square is (n-1) * (n-1), which is . Our total number of circles is about half of that, so , which is still . Remember: with big O notation, we throw out the constants.
If we had started from n instead of n-1 we'd have , which again is still since in big O notation we drop the less significant terms.