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

In place — where it appears

A claim that a procedure uses no auxiliary space beyond a constant, which for a recursive sort is usually false by a logarithm. For a recursive sort it is usually false by a logarithm, which is a factor the phrase conceals and a stack depth makes visible.

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

peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

Measuring what an algorithm keeps

Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

space · Space peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three14log nQuicksort, random pivot32log nQuicksort, first-element4,097nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, already sorted inputone slot = one array element or one stack frame

In place is a claim, and it is usually wrong about quicksort

Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.

wrong · Space

Named alongside it

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

Auxiliary spaceQuicksortRecursion depthAllocatorComparison countCost modelGuaranteeInstrumentationPartitionPeak and totalPivotRotation

All concepts