Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Stirling's approximation — where it appears

An approximation to the factorial accurate enough that its logarithm can stand in for a comparison-sorting floor at any size worth drawing. Its logarithm stands in for a comparison-sorting floor at any size worth drawing, and the agreement between the two is itself asserted rather than assumed.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons

The floor under every comparison sort

No algorithm that sorts by comparing pairs of elements can average fewer than log₂(n!) comparisons. Not one that exists, and not one that ever will. The argument takes three sentences, it is about counting leaves in a tree, and it is one of the few results in this subject that is genuinely about every possible algorithm rather than about a particular one.

floors · Floor -50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula

A limit is not a prediction

Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.

bounds · Bound comparisons (bar length is log-scaled)sorting, floor43,250sorting, merge sort43,976searching, floor13searching, binary13searching, linear4,096green outline: a proved floor · blue: a measured run3,327× between the two floors

The floor moves when the question does

Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.

floors · Floor

Named alongside it

The objects these essays reach for when they reach for this one.

Counting sortInformation theoryLower boundAccess patternAsymptotic analysisBinary searchCacheClosed formComplexity classCutoffDecision treeExtrapolation

All concepts