Big-O, and the four growth rates you will meet

The question Big-O answers

When the input doubles, what happens to the work? That is the only question Big-O notation answers. It ignores the constant factors, the hardware and the language, and keeps just the shape of the growth. That sounds like throwing away everything useful, and yet it is the single most predictive thing you can know about a piece of code before running it, because the shape decides whether a job that took a minute on a thousand rows takes an hour or a decade on a million.

Four shapes

Take n items and a machine doing a billion simple operations a second.

• O(log n): each step halves the problem. Binary search in a sorted list; finding a key in a balanced tree. At n = 10^9, thirty steps. Effectively free at any scale.
• O(n): look at everything once. Summing a column, scanning a file, one pass of a tokeniser. At n = 10^9, one second.
• O(n log n): look at everything, a logarithmic number of times. Sorting. At n = 10^9, thirty seconds. This is the cost of "sort it first", and it is nearly always affordable.
• O(n²): compare everything with everything. At n = 10^6, 10^12 operations: seventeen minutes. At n = 10^9, 10^18: thirty-one years.

The gap between the third and fourth lines is the gap that matters. Anything up to n log n scales to any dataset you will meet. Anything quadratic scales to about a million and then stops, and the next lesson but one is about recognising it.

There is a fifth shape, O(2^n), for problems where every subset must be tried. At n = 60 it is thirty years; at n = 100 it is longer than the universe. Exact solutions to such problems are not slow; they are unavailable, and the field's answer is to approximate.

Why the constants are dropped, and when they matter

3n² + 200n + 5000 is O(n²) because for large n the first term is all that counts: at n = 10^6, the 3n² is 3 × 10^12 and the rest is 2 × 10^8, a rounding error. Big-O keeps the term that wins.

But the constants are real, and two O(n) implementations can differ by a factor of a hundred. A Python loop adding a million numbers takes about 50 milliseconds; numpy.sum on the same array takes half a millisecond. Same shape, hundred-fold constant. The rule: Big-O tells you whether the approach can work; the constant tells you whether it will be pleasant. Fix the shape first, because no constant rescues n² at a billion. Then fix the constant, because a hundredfold is a hundredfold.

The trap in one character

seen = []                     # list
for item in stream:
    if item in seen:          # O(n) scan every time
        continue
    seen.append(item)

item in seen on a list scans the whole list. Inside a loop over n items, that is n scans of up to n elements: O(n²). Change one word:

seen = set()                  # set

and item in seen becomes a hash lookup, O(1), and the loop is O(n). On a million items the first version takes hours, the second a second. This is the most common accidental quadratic in data code, and the lesson on hashing explains what the set is doing that the list is not.

Memory has a shape too

The same notation describes space. A similarity matrix between n embeddings has n² entries. At n = 10^5 and four bytes each, that is 40 GB, which does not fit in a laptop's RAM, and the code that builds it will not fail with a helpful message; it will swap for an hour and then be killed. A pairwise matrix is O(n²) memory whatever you do with it, and the fix is the same as for time: do not build it.

Amortised, and average

Two refinements you will meet. Appending to a Python list is O(1) amortised: occasionally the list must be copied to a bigger block, which costs O(n), but that happens rarely enough that the average per append is constant. And hash lookups are O(1) on average; a pathological set of keys that all collide gives O(n), which is why languages randomise their hash functions.

What Big-O cannot see

It cannot see the difference between reading from RAM and reading from disk, which is a factor of a thousand. It cannot see that a GPU does a thousand things at once, so an O(n) loop and an O(n) matrix operation take very different times. It cannot see cache. The lesson on arithmetic intensity is about exactly the costs Big-O is blind to. Use both: Big-O for whether the shape survives scale, and the arithmetic of bytes and FLOPs for how long it will actually take.

The habit

Before running anything on the full data, ask: when n doubles, does this double, or quadruple? Time it on a thousand rows and on two thousand. If the second run takes four times as long, you have a quadratic, and now is the moment to fix it, not at a million.