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

Allocator — where it appears

The machinery handing out memory, whose cost model is total allocation rather than peak, and which therefore ranks structures differently from a memory limit. It charges total allocation rather than peak, so it ranks structures differently from a memory limit and neither ranking is wrong.

Named by 5 essays across 3 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 0%25%50%75%12345×1.125×1.25×1.5×2×3×4capacity left unused at the endamortised cost per append20,000 appends, cost = 1 write + a copy on resizeneither end wins

Choosing a growth factor

When a dynamic array fills up, how much bigger should the new one be? Doubling costs 2.02 units per append and leaves 39% of the allocation empty. Growing by an eighth costs 9.89 and leaves 10%. Every factor is a trade between time and space, no factor wins on both, and real implementations disagree about the answer for reasons that are measurable.

structures · Structure pale: total slots ever allocated · dark: peak held at onceone buffer, allocated once16,38416,400peak 100% of na buffer per merge229,37616,386peak 100% of nn = 16,384, random input208,687 comparisons each — identical in time

The space the model does not see

A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.

space · Space 0%25%50%75%100%1×1.5×2×3×4×6×shareheadroom over the mean occupancyoverflowingstanding idledrifting · 4.0 s window · 100 Hz47% overflow at the mean

Sized for a rate that does not hold still

A four-second window on a stream at a hundred arrivals a second holds four hundred items on average and between 105 and 2,169 when the rate moves. An allocation set at that average overflows at 47 per cent of instants while 35 per cent of it stands empty, which is the same decision failing in both directions at once.

practice · Window ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14%

The tuples a summary does not report

A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

space · Space

Named alongside it

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

Auxiliary spaceCost modelMeasurementPareto frontierPeak and totalPeak spaceQuicksortTime space tradeoffTrade offAmortised analysisArrival processBranching program

All concepts