Empirical complexity
Every other tool here shows one run of one algorithm. This one shows the shape of the cost curve, measured rather than asserted: run an algorithm at a ladder of input sizes, count its operations, and plot the measured counts against the bound it is supposed to obey. It is the tool that answers “is this actually O(n log n)?” with a picture and a number instead of a claim — and that is willing to report that the claim it was handed is not tight, which is what happens on the naive Fibonacci page.
The counts are operations, not seconds. That is deliberate: an operation count is the same on every machine and in every browser, so a link reproduces a measurement exactly, where a timing would reproduce a mood. It also means none of this says anything about the constant factors that decide which of two algorithms in the same class is actually faster.
10 subjects
- Array indexO(1)Reads one element by its position, which takes the same single operation whether the array holds eight numbers or a hundred and thirty thousand — the only flat line in the catalogue, and the one every other curve is read against.n is a list lengthup to n = 131,072
- Binary searchO(log n)Halves a sorted list until nothing is left, so every doubling of the input costs exactly one more probe — and the curve is the reason a logarithm is not a straight line on log-log axes.n is a list lengthup to n = 131,072
- Linear searchO(n)Reads every element in turn looking for one that is not there, so the count is exactly n — the reference curve at gradient 1, against which every steeper and every flatter curve is read.n is a list lengthup to n = 131,072
- Insertion sortO(n) sorted · O(n²) otherwiseShuffles each element back to where it belongs, which on an already-sorted list is one comparison each and on a reversed list is all of them — the same code on two curves, and the reason "insertion sort is O(n²)" is a half-truth.n is a list lengthup to n = 4,096
- Selection sortO(n²)Finds the smallest of what is left and swaps it into place, scanning the whole remainder every time — so it is quadratic on sorted, shuffled and reversed input alike, which is what makes insertion sort’s sensitivity to shape a real property rather than a coincidence.n is a list lengthup to n = 4,096
- Merge sortO(n log n)Halves the list, sorts each half, then merges the two in one pass — so every element is touched once per level and there are only log n levels, which is the curve that makes "asymptotically better" worth a picture.n is a list lengthup to n = 131,072
- QuicksortO(n log n) shuffled · O(n²) sorted or reversedPartitions around a pivot and recurses on both sides, which on shuffled input is O(n log n) and on already-sorted input — with the last element as the pivot — collapses onto the same quadratic curve as selection sort.n is a list lengthup to n = 131,072
- Brute-force three-sumO(n³)Examines every triple of numbers looking for three that add to zero, which is n choose 3 triples — the cubic curve, and the third gradient that turns "the gradient is the exponent" into something checkable rather than a claim about one line.n is a list lengthup to n = 512
- Naive FibonacciO(2ⁿ)Recomputes every subproblem from scratch, so the call count roughly multiplies by 2.6 for every 2 added to n — and the measurement says the textbook O(2ⁿ) is a correct upper bound and a loose one.n is a recursion argumentup to n = 32
- Memoised FibonacciO(n)The identical recursion with every answer written down the first time it is worked out, which turns an exponential into 2n − 1 calls — the same code, the same page, and seven decades of difference on one pair of axes.n is a recursion argumentup to n = 78
Nothing matches that. Clear the filter to see all 10.
Nine of these ten are also step-by-step pages in AlgoLab andRecursion, which show how they work where this one shows how they grow. Traversal and shortest paths live in Graph algorithms, tables inDynamic programming, and pattern matching in String matching.