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

Information theory — where it appears

The counting of how much a message or an answer can carry, from which floors follow that bind every possible method rather than a particular one. Its floors bind every possible method rather than a particular one, which is what separates them from a bound measured off an implementation.

Named by 2 essays across one field — 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 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 sortLower boundStirling's approximationAccess patternBinary searchCacheComplexity classDecision treeFactorialOptimalityWorst case

All concepts