What is Big O notation

Count steps, not seconds

Seconds are misleading. On a fast computer, even a slow method looks quick.
So instead of seconds, we count how many steps the work takes.
With n boxes, each method takes a different number of steps.

Pick an input size to see how many steps each method takes. (one by one = n steps · by halves = far fewer)

With only a few boxes, the two look about the same.
With 8 boxes, one by one takes 8 steps and halving takes 3, so the gap is small.
But what happens when the boxes grow a lot?

What happens as n grows

This is where the real difference shows.
As n grows, one method's work grows only as fast as the boxes do, while another's jumps to four times the work every time the boxes double.
n times n is written n².

Each press of the button doubles the boxes. n grows with the boxes, but n² shoots up faster and faster.

n² gets frightening when there are many boxes.
With 100 boxes, n is 100 and n² is 10,000. With 1,000 boxes, n is 1,000 and n² is a million.
It starts small but quickly gets out of hand.

Comparing the curves

Put the three kinds of growth side by side and you can see it at a glance.
log n barely rises, however many boxes there are.
n climbs in a straight slant, and n² bends upward and shoots far above the rest.

Turn the curves on one at a time and compare. At the same n, log n, n, and n² reach completely different heights.

Now it's clear why halving was so fast.
Halving is log n: even with a thousand boxes, it's done in about ten steps. One by one is n: a thousand boxes means a thousand steps.
The shape of the growth decided the winner.

Keep only the biggest term

Count the real steps and you often get a messy formula like 3n² + 5n + 9.
But once n gets very large, n² overwhelms everything else.
So we erase the small terms and keep only the fastest-growing one, n².

Each press erases a small term or the number in front. In 3n² + 5n + 9, only n² is left when n is large, and the mark for that shape is big O.

We drop the number in front, too. Whether it's 3n² or 100n², the shape of the growth is still n².
So we simply write O(n²).
Big O is a one-line label that says how something grows when the input is large.

How far we've come

To sum up, speed is measured not in seconds but by the shape of growth.
As n grows, log n barely rises, n rises with the boxes, and n² explodes.
However messy the formula, you only need to look at the biggest term, and the mark for it is big O.

Turn on the three terms one by one to sum it up in a line. log n stays nearly flat, n slants upward, n² explodes. Only the biggest term matters.

Now, looking at a method, you can judge whether it's fast without timing it.
If doubling the boxes doubles the work, that's fine; if the work quadruples, be careful.
A good method is one that grows slowly even in the face of a big job.