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) + n

Or, equivalently, the other way around:

n + (n-1) + ... + 3 + 2 + 1

And sometimes the last n is omitted, but as we'll see it doesn't affect the big O:

(n-1) + (n-2) + ... + 3 + 2 + 1

Let's draw this out. Let's say n=10, so we'll represent n-1 as nine circles:

A row of 9 circles.

We can continue the pattern with n-2

2 rows of circles: 9 on top, 8 on the bottom.

And n-3, n-4, etc, all the way down to 1:

9 rows of circles: 9 on top, and one fewer circle in each row, down to 1 circle on the bottom.

Notice both the top and right "sides" of our set of circles have n-1 items:

In a right triangle formed by 9 rows of circles (9 in the top row, down to 1 in the bottom row) the top and left side of the triangle are 9 circles long.

In fact, we could imagine our circles inside of a square with sides of length n-1:

A square around 9 rows of circles (9 in the top row, down to 1 in the bottom row) so the square is 9 by 9 circles.

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.