Big O race

Pick an input size. The five tasks run on the same random input and count their operations: a single array read for the constant-time task, key comparisons for the others. Then the race replays those counts on one clock. Insertion sort's count is computed exactly from the input's inversions rather than by running it, because at a million items it would need about 249,999,750,000 comparisons; the count is checked against a real insertion sort in tests.

• At 10 items all five finish within a few dozen operations; the classes are hard to tell apart.
• At 1,000, insertion sort needs 244,053 comparisons and merge sort 8,707.
• At 1,000,000, binary search still needs only 20 comparisons, while insertion sort's lane would take minutes at a nanosecond per comparison.

Big O notation is a way of describing how the cost of an algorithm, usually its running time or memory, grows as its input gets larger. Instead of counting exact steps, which depend on the language, the machine and the details of the code, it keeps only the part that dominates for large inputs. An algorithm that takes 3n + 50 steps and one that takes 100n steps are both O(n): doubling the input roughly doubles the work.

Formally, f(n) = O(g(n)) means there are constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. The constant c absorbs differences in speed per step, and n₀ says that only large inputs count. That is what makes Big O useful for comparing algorithms, and also why it says little about small inputs.

The best way to read a complexity class is to ask what happens when the input doubles. The last column comes from the simulator's own counts, going from 10,000 to 20,000 items.

Operations counted by the simulator on its default input at each size:

Because Big O drops constant factors, a worse class can be faster on small inputs. Take two algorithms costing 3n + 50 and n²/100 steps. The quadratic one is cheaper until n = 315 and more expensive from n = 316 onward, and the gap then keeps widening.

Library sorts use this: Timsort, introsort and pattern-defeating quicksort all switch to insertion sort for short pieces. It is not that insertion sort makes fewer comparisons. Averaged over random inputs, it makes 5.0 comparisons at 4 items against merge sort's 4.7, and 72.4 against 45.7 at 16. It wins on everything else: no recursion, no buffer, a tight loop over adjacent memory. Counting operations is a model, and the model leaves out the cost per operation.

Big O gives an upper bound: a function that is O(n) is also, strictly, O(n²). Big Omega, Ω, gives a lower bound, and Big Theta, Θ, says both at once: the function grows at exactly that rate, up to constant factors. Merge sort is Θ(n log n); binary search is Θ(log n) in the worst case. Donald Knuth argued in 1976 for using Ω and Θ in this way in computer science, and that is now standard in textbooks, though in everyday speech "Big O" usually means the tight bound.

An algorithm can have different bounds for different inputs. Quicksort is O(n log n) on average but O(n²) in the worst case; insertion sort is O(n) on input that is already sorted but O(n²) on average. Unless said otherwise, a stated complexity usually means the worst case.

Amortized cost averages over a sequence of operations. Appending to a dynamic array, such as a Python list or a C++ vector, is usually cheap but occasionally copies every element into a larger array. If the capacity doubles each time, a million appends cause 1,048,575 element copies in total, about one per append, so appending is O(1) amortized even though a single append can be O(n).

Big O applies to memory as well as time. Merge sort needs O(n) extra space and heapsort O(1); a recursive algorithm needs stack space proportional to its recursion depth.

Time taken at one operation per nanosecond, ignoring constant factors:

The O symbol comes from number theory. Paul Bachmann introduced it in 1894, in the second volume of his Analytische Zahlentheorie, and Edmund Landau adopted and popularised it, so O and its relatives are also called Landau symbols. Hardy and Littlewood introduced a version of Ω in 1914. Computer scientists took up the notation to analyse algorithms in the 1960s, and Knuth's 1976 note "Big Omicron and big Omega and big Theta" fixed the definitions of Ω and Θ that computer science now uses.