Hamish Humbert

I'm learning Big O for myself. The best way I know to prove I actually get it is to explain it. So I tested it.

I asked my laptop to add up every number from 1 to 10,000,000. Two ways.

The loop took 2.9 seconds.
The formula took 0.001 milliseconds.

Same answer, 50,000,005,000,000. One did ten million additions. The other did one calculation.

That gap is Big O. It's how your code slows down as the data grows.

Two words you need first

n is the size of the input. Basically how much stuff you hand your code. Five numbers, n is 5. Ten million numbers, n is 10,000,000.

A step is one small piece of work. Adding two numbers. Checking one item. Comparing two things.

So my loop, with n at ten million, takes ten million steps.

Seconds lie, steps don't

Here's the bit that made it click for me. I ran the exact same loop five more times. Same laptop, same numbers.

3.1 seconds. 2.9. 10.9. 11.5. 5.4.

My laptop was clearly busy with something else, and the times were all over the place. The steps? 10,000,000. Every single time.

Turns out this is a known problem. Researchers have shown that tiny changes to how a program is set up can swing its measured speed (Mytkowicz et al., 2009). So Big O counts steps.

What the O means

The O stands for "order of". You read O(n) as "grows like n".

It's not an exact count. It's the shape: if I give my code ten times more data, how much more work does it do?

That's also why it drops the small stuff. If something takes n + 1 steps, that extra one doesn't matter at ten million. It's just O(n).

Experiment 1: loop vs formula

def add_up_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

def add_up_formula(n):
    return n * (n + 1) // 2

I tried three sizes, each 100 times bigger than the last. The steps grew exactly 100 times each time. The time grew too, just messily: 0.16 ms, then 32 ms, then 2.9 seconds.

That's O(n), linear time. Think of reading a long receipt line by line looking for one item. Longer receipt, more reading.

The formula did one calculation at every size, about a thousandth of a millisecond each time. That's O(1), constant time. Like walking straight to locker 50. Doesn't matter how long the hallway is.

(The formula is the trick Gauss is said to have used as a schoolboy.)

Experiment 2: cut it in half

Think of guessing a number between 1 and 100 where I tell you higher or lower. Guess the middle every time and each answer throws away half of what's left. You never need more than seven guesses.

Searching a sorted list works the same way. Finding the last item in 1,000 items took 1,000 looks one by one. Halving took 10.

At 1,000,000 items: 1,000,000 looks vs 20.

A thousand times more data and halving needed 10 more looks. That's O(log n), logarithmic time. It's how a database index finds one record among millions.

The catch: the data has to be sorted.

Experiment 3: the loop inside a loop

Picture a room where everyone shakes hands with everyone else, once. 100 people make 4,950 handshakes.

Checking a list for duplicates by comparing every item with every other item is the exact same problem. A loop inside a loop.

100 items: 4,950 comparisons.
1,000 items: 499,500.
10,000 items: 49,995,000.

Ten times the items, about a hundred times the work. That's O(n²), quadratic time, and honestly it's the easiest slow code to write by accident.

The fix is simple. Walk the list once and remember what you've seen in a set. 10,000 steps at 10,000 items. That's O(n) on average, because a set usually answers "seen this before?" in one step, just not always.

Experiment 4: sorting

Halving needs sorted data, so how fast can you actually sort?

Good sorts split the list in half again and again (that's log n rounds) and touch every item each round (that's n). So the work grows like n log n. That's O(n log n).

I counted every comparison Python's built-in sort made on a shuffled list. 8,655 at 1,000 items. 1,531,978 at 100,000. Close to n log n (1,660,964). Nowhere near n² (10,000,000,000).

For sorts that compare items, n log n is about the best you can do. That's a proven limit.

The far end: O(n!)

Imagine a delivery driver trying every possible order of their stops. That's O(n!), factorial time. 10 stops is 3,628,800 orders. 20 stops is about 2.4 quintillion. At a billion a second, that's around 77 years.

Real route planners don't do this. Back in 1962, Held and Karp found the exact best route far faster than trying every order, but it's still too slow for big problems. So real apps use clever shortcuts that find very good routes quickly.

The six shapes, fastest to slowest

Here's every shape on one chart. Left to right is more data. Bottom to top is more work. The flatter the line, the better your code holds up as the data grows.

• O(1), constant: the same work however much data. Like walking straight to locker 50. Grabbing the 100th item in a list.
• O(log n), logarithmic: every step cuts the problem in half. Like the guessing game. Finding a record with a database index.
• O(n), linear: double the data, double the work. Like reading a receipt line by line. Searching an unsorted list.
• O(n log n): a bit more than linear. Like splitting and merging a hand of cards. Every good sort button.
• O(n²), quadratic: ten times the data, a hundred times the work. Like everyone shaking hands. A loop inside a loop.
• O(n!), factorial: off the chart almost straight away. Like trying every delivery route. Brute-force search.

Where Big O misleads

It's about growth, not speed at your size. On tiny inputs a "slower" method can actually win, which is why fast sorting code switches to a simple sort for small chunks (Sedgewick, 1978).

And one Big O usually means the worst case. Quicksort averages about n log n (Hoare, 1962) but can drop to n² on unlucky input, like a list that's already sorted (Sedgewick, 1978).

Why it's worth knowing

Data grows. An app with 100 users today might have 1,000,000 next year. That's 10,000 times more users.

Linear code does 10,000 times more work. Quadratic code does 100,000,000 times more.

Big O lets you spot that before your users do. It's the same reason I care about getting 1% better every day. Small things compound, and in code that works against you too.

Quick recap

1. Count steps, not seconds.
2. n is the size of the input, and Big O is the shape of how the work grows.
3. Halving beats checking everything, as long as the data is sorted.
4. Watch out for a loop inside a loop.

Takeaway

Next time you write code, ask it one question: if the data were ten times bigger, how much more work would this do?

If the answer hurts, it's usually a loop inside a loop.

Run it yourself

Every number here came from five short Python scripts. Plain Python 3, nothing to install. Download them all, then run python run_all.py.

• exp1_add_up.py: loop vs formula
• exp2_search.py: check every item vs halving
• exp3_duplicates.py: every pair vs remember what you've seen
• exp4_sorting.py: counting the comparisons Python's sort makes
• bonus_timing.py: the same loop, five runs

Your times will differ from mine. Your step counts won't.

Further reading

If this clicked and you want more: Ned Batchelder's talk Big-O: How Code Slows as Data Grows, Harvard's CS50 lecture on algorithms, and the Python wiki's TimeComplexity page for what everyday operations cost.