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

The thread: A limit is not a prediction

An asymptotic bound describes behaviour as n grows without end. It does not say which of two algorithms is faster at the size anyone will actually run, and treating it as though it does is the commonest error in the subject.
10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly What a bound is

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.

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

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.

 0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point What the machine does

The cliff where the data stops fitting

Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.

 -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 What a bound is

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.

 1234560.000.250.500.75formulameasuredload factor αprobes per insertion8,192 slots, mean of 8 fills, seeds stated in lib/structures.jstwo routes agree to 2.3% What is taught wrongly

The probe formula nobody checks

The expected number of probes to insert into a hash table under linear probing is ½(1 + 1/(1−α)²). It is quoted constantly, it is correct, and applied to a table of 256 slots at 95% load it overstates the measured cost by nearly half — because it is an asymptotic result and a real table is not asymptotic.

All themes