Big-O Race Simulator
Five algorithms, five complexity classes, one input size. Slide n from 10 to 100,000 and watch how the gap between O(log n) and O(n²) opens up fast. At small n they all finish about the same time; past n = 1,000 the lanes diverge dramatically.
Five lanes, five complexity classes, all racing on the same input size n. Each bar fills as its algorithm burns through the operations it needs — one for O(1), n × n for O(n²) — and every lane spends operations at the same rate, so the finish order is decided purely by how much work each class demands. The counters on the right of each lane show the exact operation counts.
Try the small end first: set n to 10 and all five lanes finish in a near tie. Big-O tells you nothing at small inputs, which is why the nested loop in your prototype felt fine. Then drag n to 100,000. O(n²) now needs ten billion operations against O(n log n)'s 1.7 million, and the quadratic lane essentially stops moving. What should surprise you is how late the divergence arrives and how total it is once it does — the same code goes from indistinguishable to unusable in two orders of magnitude of n.
What Big-O actually says
It's not about speed. It's about growth.
Big-O notation describes how the time (or space) an algorithm uses grows as the input grows. O(n) means "if I double the input, the work roughly doubles". O(n²) means "if I double the input, the work quadruples". O(log n) means "if I double the input, the work goes up by exactly one step".
The "O" hides constants and lower-order terms because they don't
matter at scale. An algorithm that's 3n + 50 is
O(n); one that's n² / 100 is O(n²). At small n the
second one is faster — but cross n = 30,000 and the first wins
forever. That crossover is what Big-O captures.
Where each class shows up in real code
A taxonomy you'll use forever.
| Class | Examples | n = 1M takes about |
|---|---|---|
| O(1) constant | Hash-map lookup, array index, push/pop on a stack. | 1 ns |
| O(log n) logarithmic | Binary search, balanced-tree insert, heap push. | 20 ns |
| O(n) linear | Array scan, hash-map iteration, linked-list traversal. | 1 ms |
| O(n log n) linearithmic | Merge sort, quick sort (average), heap sort, building a sorted index. | 20 ms |
| O(n²) quadratic | Bubble sort, naive duplicate detection (compare every pair), inserting n items into an unsorted array. | 17 minutes |
| O(2ⁿ) exponential | Naive Fibonacci recursion, brute-force subset enumeration, naive travelling salesman. | longer than the universe is old |