When Big-O Lies

Big-O describes how cost grows, and it gets there by throwing away constants, lower-order terms and the entire memory hierarchy. The cost model of Chapter 1 charges every memory access one step, and the latency ladder showed that a step can cost 1 nanosecond or 100. For large enough inputs the growth rate always wins, but "large enough" can lie beyond any input the program will ever see.

One of Lantern's postings lists shows when the cheaper-looking algorithm loses, and the discipline that follows from it is short: analyse to choose the candidates, then measure to choose the winner.

What the Notation Throws Away

O(log n) and O(n) say nothing about the price of one step. Take an algorithm that costs n steps of 1 nanosecond each, and another that costs log n steps of 100 nanoseconds each. The second has the better class. They cost the same when n equals 100 times log n, which happens near n equal to 1,000. Below that point the "worse" algorithm is the faster one.

Every constant moves the crossover. Make the slow step 1,000 nanoseconds and the crossover moves out past 10,000 items. The curves still cross eventually, which is what Big-O promises. It does not promise that the crossing happens at a size you have.

Small n Is the Common Case

Most collections in real programs hold tens or hundreds of items: a request's headers, a user's roles, a configuration's keys, the fields of a record. At those sizes the constant decides, not the growth, and a structure with a tiny constant beats one with a better class.

Production libraries encode this. Python's sort finishes short runs with binary insertion sort, an O(n²) algorithm, because it wins on short runs (Chapter 7). A B-tree node (Chapter 6) holds a few hundred keys and searches them as a flat, sorted array rather than as a tree of its own. Both designs use Big-O the way it is meant: the better class where n is large, the smaller constant where it is not.

A Scan Beating a Tree

A rare subject term in Lantern's index has a postings list of 40 record ids. Stored as a packed, sorted array of 8-byte ids, it takes 320 bytes, five consecutive 64-byte cache lines. A straight scan reads them in order while the prefetcher (see Caches and Locality) fetches ahead. The whole search touches five lines, most of them already on the way.

Store the same 40 ids as a balanced binary tree instead, one separately allocated node per id, and the tree is six levels deep. Each level is a pointer to wherever the allocator happened to put that node. A lookup follows six pointers, and each fetch can start only when the one before it has arrived, so on a cold cache it can pay six dependent misses at about 100 nanoseconds each. The O(n) scan wins. A binary search over the same array wins too, because it also stays inside five lines.

The Interpreter Is a Constant Too

In pure Python each step costs tens of nanoseconds of interpreter work (Chapter 13) on top of its memory cost. On CPython 3.15, a loop that does nothing costs about 10 nanoseconds per trip, and one that adds a number about 35. So a search written as a Python loop pays per element roughly what compiled code pays per cache line.

def tree_find(node, x):          # a Python loop over node objects
    while node is not None:
        if x == node.key:
            return True
        node = node.left if x < node.key else node.right
    return False
bisect.bisect_left(ids, x)       # compiled binary search over one list

The first function walks a binary search tree built from Python node objects, one interpreted step per level. The second line hands the same job to the standard library's binary-search module, which runs in compiled code over one sorted list. Measured on CPython 3.15 with 40 ids, the tree took about 160 nanoseconds per lookup and the binary search about 80. Even a plain membership test on the list, a linear scan in compiled code, took about 175 nanoseconds, a tie with the tree that has the better Big-O.

The practical rule for Python follows. A structure searched by built-in code, such as a set, the binary-search module, or membership on a short list, beats a structure searched by a Python loop over node objects, whatever their classes, until n is large.

Measure After You Analyse

The constants buy a range, not immunity. The same scan over a popular term's postings list of 400,000 entries reads 3.2 megabytes and loses to anything logarithmic. On CPython 3.15, a membership scan over 400,000 ids took about 4.5 milliseconds per lookup, while the binary search took about half a microsecond. And the quadratic loop that was fast in tests still ends the project at a million items, as Chapter 1 showed.

So analysis and measurement have different jobs. Analysis says which candidates can possibly work at the production n, and what shape their cost should have as n grows. A measurement at production size, with production data, run cold as well as warm, says which of the surviving candidates wins. Neither replaces the other.

The Cost in a System You Run

At Lantern's Saturday peak of 300 searches a second, the time difference between the array and the tree is microseconds per search, invisible next to a single network round trip. The memory difference is not invisible. Packed ids cost 8 bytes each. A separately allocated tree node carries the id, two child pointers and the allocator's own header, several times the payload, and as a Python object far more.

Suppose the postings are most of Lantern's 1.8-gigabyte index. As packed ids they fit comfortably on the 8-gigabyte server. As tree nodes five to ten times larger, the same postings would need 9 to 18 gigabytes, more than the server has. The layout that wins the benchmark is also the only one that fits.