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

The thread: The constant is the content

Three sorts are all Θ(n log n) and their measured comparison counts differ by a factor of three. The class is what they have in common; the constant is what distinguishes them, and it is the part that gets dropped.
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.

 comparisons ÷ n log nMerge sort0.855Merge sort with a cutoff0.992Quicksort, random pivot1.018Quicksort, first-element1.082Quicksort, median of three1.117Shellsort1.246Heapsort1.649all of these fit n log n1.9× between best and worst What a bound is

The constant the notation drops

Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.

 the floorMerge sort1.02×Quicksort, first1.23×Quicksort, random1.24×Merge sort + cutoff1.29×Quicksort, median-31.32×Shellsort1.45×Heapsort1.96×Insertion sort9.69×Bubble sort19.26×Selection sort19.38×floor = log₂(256!) = 1,684 comparisonsmean of 16 runs, against a proved bound The floors

How close anything gets to the floor

The interesting question about a sorting algorithm is not its complexity class but its distance from the bound nothing can cross. Merge sort comes within 2.2% of the information-theoretic floor. Heapsort uses 96% more than it needs to. Selection sort uses nineteen times. Those three numbers say more than the classification does.

 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 Structures

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.

All themes