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

Power law — where it appears

A quantity falling as a fixed power of its argument rather than as an exponential, so that it keeps a long tail instead of a cliff. On logarithmic axes it is a straight line whose slope is the exponent, which is why growth is plotted on those axes here.

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

10010³10010³10⁴10⁵10⁶ncomparisonsInsertionMergeHeapsortQuicksorta power law is a straight line herecomparisons, counted exactly

Fitting a class to measurements

A complexity class is normally read off the shape of the loops and written down. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is granted a class only if the fit holds — which turns a statement about code into a statement that can fail.

counting · Count 010200100200seconds since the burstestimated rate, arrivals a secondthe burstexponentialexact polynomialthree exponentialsrestarted forwardfaint: the same streamswith the burst removedmatched at 5.0% spread · burst of 300 in one secondthe same event, four descents

What a heavier tail actually buys

Four decays, each tuned until it is equally quiet on a stream with nothing happening, then given one burst. At a burst of three hundred they see it for 54, 63, 68 and 104 seconds — indistinguishable. At nine thousand the exact polynomial reaches 384 seconds and the exponential 156. The shape of a tail does not decide how far back a scheme can see. It decides how fast that distance grows with the size of the event, and the exchange rate is the reciprocal of the exponent.

streaming · Decay

Named alongside it

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

Complexity classCurve fittingDesign parameterEstimatorExponential decayFalse alarmFalsificationFittingForward decayHalf lifeHonest limitMeasurement design

All concepts