An algorithm is a precise, finite recipe that turns an input into an output: a list of names into a sorted list, a map into a shortest route, a number into its prime factors. Before any programming language gets involved, algorithms can be compared on one question: how much work do they do as the input grows?
Count steps, not seconds
Timing a program measures the program, the compiler and the machine all at once. To compare algorithms, we count their basic operations instead — comparisons, swaps, array reads — as a function of the input size n. The count doesn't depend on the CPU, and it shows how the cost grows. For large inputs, the growth is what matters.
Here are two ways to look for a value in a list of 32 numbers. Linear search checks each element in turn. Binary search only works on a sorted list: it looks at the middle, throws away the half that can't contain the value, and repeats.
Initial array.
Linear search — Checks every element left to right until it meets the target. Best O(1), average O(n), worst O(n).
Initial array.
Binary search — Needs sorted input: each probe of the middle element halves the range lo..hi. Best O(1), average O(log n), worst O(log n). The generated array is sorted first.
Switch the target to absent — the worst case — and look at the cost vs n chart under each demo. Linear search makes one comparison per element: 8, 16, 32 … 256. Binary search halves the range at each step, so it needs 3, 4, 5 … 8 comparisons. Doubling the input adds one step. At a million elements, that's 20 comparisons against a million.
| n | linear search | binary search |
|---|---|---|
| 8 | 8 | 3 |
| 32 | 32 | 5 |
| 256 | 256 | 8 |
| 1,000,000 | 1,000,000 | 20 |
Big-O notation
Big-O describes how a cost grows, ignoring constant factors and small inputs. Formally, a cost f(n) is O(g(n)) if there are constants c and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀. In practice: keep the fastest-growing term and drop its coefficient. For example, 3n² + 5n + 20 is O(n²).
The classes you'll meet most often, with the time they'd take at n = 1,000,000 if each step took a nanosecond:
| Class | Name | Example | n = 10⁶ |
|---|---|---|---|
| O(1) | constant | reading a[i] | 1 ns |
| O(log n) | logarithmic | binary search | 20 ns |
| O(n) | linear | linear search, summing an array | 1 ms |
| O(n log n) | linearithmic | merge sort, heap sort | 20 ms |
| O(n²) | quadratic | insertion sort, comparing all pairs | 17 minutes |
| O(2ⁿ) | exponential | trying every subset | longer than the age of the universe |
Each step down the table is a different world. No faster machine rescues an O(n²) algorithm on a large enough input, and a better algorithm often gains more than any hardware upgrade.
Best, worst and average case
The same algorithm can do very different amounts of work on inputs of the same size. Insertion sort takes each element and slides it left until it's in place:
Initial array.
Insertion sort — Grows a sorted prefix; each new element sinks left until it meets a smaller one. Best O(n), average O(n²), worst O(n²).
On 16 reversed elements, every new element has to travel all the way to the front: 120 comparisons, that is n(n − 1)/2. Switch the input to sorted: 15 comparisons, one per element. On random input it's in between, 88 here. At n = 256 the gap becomes 255 comparisons for sorted input, 15,874 for random, and 32,640 for reversed.
So "insertion sort is O(n²)" is a statement about the worst case (and here also the average). Its best case is O(n), which is why it's excellent on data that's already almost sorted.
Worst cases hide in unexpected places. The quicksort in this visualizer picks the last element as its pivot. On random input it needs 2,325 comparisons for 256 elements, but on already-sorted input every partition is maximally lopsided, and it needs 32,640, as bad as insertion sort. Real libraries guard against this: they choose pivots more carefully and switch algorithms when a partition goes wrong. C++'s std::sort, for example, is usually an introsort, a quicksort that falls back to heap sort.
n log n versus n²
Sorting shows the gap between the two most common classes. On 256 random elements:
| Algorithm | Comparisons | Growth |
|---|---|---|
| insertion sort | 15,874 | O(n²) |
| selection sort | 32,640 | O(n²), on every input |
| quicksort | 2,325 | O(n log n) on average |
| heap sort | 3,323 | O(n log n) |
| merge sort | 1,731 | O(n log n) |
Initial array.
Merge sort — Top-down: sort each half, then merge the two sorted runs through an auxiliary buffer. Best O(n log n), average O(n log n), worst O(n log n).
Merge sort splits the list in halves down to single elements, then merges sorted halves back together. There are log₂ n levels of splitting, and each level does about n work, so the total is O(n log n).
No comparison-based sort can do fundamentally better. There are n! possible orders, and each comparison has only two outcomes, so telling them apart takes at least log₂(n!) ≈ n log₂ n comparisons in the worst case. For 256 elements that's about 1,684 — and merge sort's 1,731 is close to it.
Where the real machine bends the rules
Big-O is the starting point, not the whole story:
- Constants matter for small n. An O(n²) algorithm with a tiny constant beats an O(n log n) one on a few dozen elements. That's why real sorts — Timsort in Python and Java, introsort in C++ — switch to insertion sort on small ranges.
- Memory access patterns matter. Two algorithms with the same count can differ hugely in time because one walks memory in order and the other jumps around. The caches chapter shows a 75% versus 0% hit rate on identical work.
- Branches matter. A comparison whose outcome is random costs a misprediction about half the time; the same comparison on sorted data costs almost nothing.
- Space is a cost too. Merge sort needs O(n) extra memory for merging. Heap sort and insertion sort sort in place, using O(1) extra.
Takeaways
- Compare algorithms by counting basic steps as a function of the input size n, not by timing them.
- Big-O keeps the fastest-growing term: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
- The same algorithm has a best, worst and average case: insertion sort is O(n) on sorted input and O(n²) on reversed input.
- Comparison sorting can't beat about n log₂ n comparisons, and merge sort, heap sort and (on average) quicksort reach that bound.
- Constants, caches and branch prediction decide between algorithms of the same class.