Maths/Big O notation

When the constants come back

After thiswhat you will be able to doFind the crossover where two concrete cost formulas exchange winners, and explain why a slower-growing algorithm can lose on small inputs.

Questionwhat this lesson answersThe whole arc agreed to discard constant factors because they stop mattering eventually. Real programs run at a finite size. So at what size does the discarded constant decide which algorithm is actually faster, and why does real merge sort hand small lists to a slower-looking method?

Not coveredwhat this lesson leaves outWe compare two specific costs and find the one input size where they cross. We do not model a real machine's caches and pipelines, which are among the reasons the constants are what they are.

The arc has repeatedly discarded fixed multipliers. The agreement was that they stop changing the growth story once the input becomes large enough. A real program does not run at “large enough” in the abstract. It runs on a list with a finite number of items, and that list can be small. At those sizes, the factor we threw away can decide which program finishes first.

Consider two ways to sort a list. Start by growing a sorted part one item at a time. Take the next item and slide it back past every larger item until it belongs in the right place. This method is called insertion sort. In its worst arrangement, every new item travels past all the earlier ones. The counting lesson already found that later-pair total as the triangular number ${\dfrac{n(n - 1)}{2}}$.

The recurrence lesson built a different method: split the list, sort each piece the same way, and join the ordered pieces back together. That method is called merge sort. Its main cost grows like ${n \log_2 n}$. It also has more work for each item in this simple model: it must ask for new storage and copy items while it joins pieces. The next two expressions are illustrative step counts, not measured times on a particular machine:

The fixed ${5}$ is the constant factor. It says that each item on a merge level costs five model steps. The formula does not claim that a real copy has the same cost on every machine, or even that every machine would choose the same number. It gives the two growth shapes a concrete price so we can ask where one cost passes the other.

The two formulas count different kinds of work, but that is the point of the comparison. Insertion sort pays for nearby moves as it builds its sorted part. Merge sort pays extra work on every split level so that it can avoid making all later-item pairs. The multiplier ${5}$ stands for that extra work in one compact number. Replacing it with a larger fixed number would not change merge sort’s long-run shape, but it would make the short-list price larger.

No bound has been contradicted when the short-list winner differs from the eventual winner. A bound throws away the multiplier precisely because it refuses to decide close races at finite sizes. The full cost models keep the multiplier, so they can answer the more practical question: which method uses fewer modeled steps for this particular list length?

Comparing only what happens after the input becomes very large, while ignoring fixed multipliers, is called an asymptotic comparison. On that view, the pair count in insertion sort eventually overtakes merge sort and does not return. But the table starts with finite lists, and the winner is the opposite one for a while:

At around thirty items, insertion sort is far cheaper in this model. At sixty it is still cheaper, but only just. The curves meet between whole input sizes sixty and sixty-one, at about 60.09. A list has a whole number of items, so the first whole size on the merge side is ${61}$. The place where the two costs change their order is called the crossover. For this model, insertion wins through sixty and merge wins from sixty-one onward:

The boundary is not a magic property of sixty-one. It is the first whole input after the smooth curves have crossed. At that point the two costs are close, so a different fixed multiplier can move the answer by many list items. Far above the boundary, the gap grows quickly and the precise location of the crossing matters less to the winner.

This is the discarded constant made visible. Big O puts merge sort ahead because the shape ${n \log n}$ grows more slowly than the shape ${n^2}$ eventually. The crossover tells us where that eventually begins for these two fixed step counts. It is a concrete version of the threshold called n zero in the O(f) definition. Below a threshold, the asymptotic bound promises nothing about which implementation is actually quicker. That is the unfinished work named by both the What we agree to throw away and What O(f) actually is doors.

This is also why many sorting routines in real language libraries, called production sorts, do not use merge sort all the way down to one-item lists. They hand short pieces, often a few dozen items, to insertion sort. Below the crossover, insertion’s smaller amount of extra work beats the method with the better long-run shape. The constant returns as an engineering decision, not as a flaw in the growth argument.

The two numbers above are still a model. The real fixed costs depend on details this lesson holds still: small fast memory areas called caches, memory allocation, and the rest of the machine’s behavior. Those details can move the true crossover. That is why a real implementation measures its crossover on its target machine instead of treating this calculated ${61}$ as a universal setting. The machine model door is where those constants come from.