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

Factorial — where it appears

The number of orderings of n distinct items, n times n minus one down to one. Its base-two logarithm is the floor on the average comparisons any comparison sort needs, and its growth is what stops exhaustive enumeration of inputs beyond about a dozen elements.

Named by 2 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 every orderthe named inputsmean0102030comparisonsInsertion sort7 to 28 · named inputs reach 28Merge sort12 to 17 · named inputs reach 16Heapsort21 to 29 · named inputs reach 27Quicksort, first-element pivot13 to 28 · named inputs reach 28Quicksort, median of three25 to 29 · named inputs reach 2540,320 orders of 8 distinct elements3 worst cases unnamed

A count over every input

Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.

counting · Count

Named alongside it

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

Adversarial inputBenchmark inputBenchmarkingComparison countCounterexampleCounting sortDecision treeExhaustive searchHeapInformation theoryLower boundMeasured count

All concepts