The ruler that measures speed

Count the steps

Seconds confuse us.
On a fast computer
even a slow way looks quick.
So instead of seconds,
we count "how many steps?"
When there are n boxes,
each way
takes a different number of steps.

Pick an input size and count the steps each way takes. (One by one = n · by half = few)

With few boxes,
the two look similar.
For 8 boxes,
one by one is 8,
by half is 3.
Not much gap.
But what happens
when we grow the boxes a lot?

What happens as it grows

Here the truth shows.
Grow n, and
one way climbs
slowly, with the boxes,
while another,
when the boxes double,
jumps to four times the work.
n times n,
that is n squared.

Tap to grow n. n rises with the boxes, but n squared explodes as the boxes get bigger.

n squared is scary
when the boxes are big.
100 boxes:
n is 100,
n squared is 10,000.
1,000 boxes:
n is 1,000,
n squared is a million.
It starts small
but soon grows out of hand.

Compare the curves

Put three growths
side by side
and you see it at a glance.
log n
barely climbs
even as the boxes grow.
n rises in a straight slant,
n squared curves up
and shoots far above.

Tap to turn on curves and compare. At the same n, log n, n, and n squared reach completely different heights.

Now you see
why cutting in half
was so fast.
By half is log n:
even a thousand boxes
finish in about ten.
One by one is n:
a thousand means a thousand.
The shape of the growth
decided the winner.

Keep only the biggest term

Count the real steps and
you get a messy formula
like 3n squared + 5n + 9.
But when n gets very big,
n squared
overwhelms the rest.
So we erase the small terms
and keep only
the fastest-growing, n squared.

Tap the small terms to erase them one by one. In 3n squared + 5n + 9, when n is big only n squared remains, and that is big O.

We drop the front number too.
3n squared or 100n squared,
the shape of the growth is the same n squared.
So we just write
O(n squared).
Big O is a name tag
that writes, in one line,
"in what shape does it grow for big inputs?"

Look how far we've come

To sum up:
speed is measured not in seconds
but by the shape of growth.
As the boxes n grow,
log n barely rises,
n rises with the boxes,
n squared explodes.
However messy the formula,
you look at just the biggest term,
and that mark is big O.

Tap the three to sum it up in one line. log n nearly flat, n slanting, n squared bursting upward. Just look at the biggest term.

Now, looking at a method,
you can gauge its speed
without timing a second.
If doubling the boxes
doubles the work, fine;
if it leaps to four times, beware.
A good method
is one that grows slowly
even before a big job.