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

Limit — where it appears

What a quantity approaches as its parameter grows without bound, which is what asymptotic notation is about and is not a prediction at any size. Asymptotic notation is about it and is not a prediction at any size, which is the distinction this collection's first essay exists to make.

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

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

What O-notation does not say

Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it.

bounds · Bound -50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula

A limit is not a prediction

Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.

bounds · Bound

Named alongside it

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

RegimeThresholdAsymptotic analysisAsymptotic notationClosed formComparison countConstant factorCutoffDistributionExtrapolationFalsificationFinite size effect

All concepts