Big O notation
Drag n and watch how each complexity class grows. The gap between O(log n) and O(n²) stops being abstract when you can see it explode.
9 min read
Big O describes how an algorithm's work grows as its input grows. It deliberately throws away the details, the constant factors and the small terms, and keeps only the shape. That makes it a superb tool for one question, “what happens when n gets large?”, and a misleading one for others.
The gap is not a gap. It is a cliff
Plot the common complexity classes on the same axes and, for small inputs, they sit within a few operations of each other. That is exactly why a slow algorithm survives code review: on the test data, nobody can tell.
Then n grows. At n = 40, O(log n) is about 5 operations and O(n²) is 1,600. O(2ⁿ) is about 1.1 trillion, roughly eighteen minutes at a billion operations a second, for an input of forty items. Nothing in the code looks a trillion times worse. The shape is doing all of it.
The better algorithm is often slower, for a while
Big O drops constant factors, and in real code those constants are the difference between a tight loop over contiguous memory and a tree that chases pointers across the heap. Shape always wins eventually. “Eventually” is the question.
Give the O(n log n) algorithm steps that cost 200 times more and the quadratic one stays faster until well past a thousand items. This is not a curiosity. It is why real sorting routines switch to insertion sort for runs under about 16 elements, and why an asymptotically worse algorithm on an array routinely beats a better one on a linked structure.
It does not mean constants beat shape. Past the crossover the quadratic algorithm loses, by more at every step. It means the useful question is never “which complexity class?” on its own, but “which class, at the n I actually have?”
Which of these can you actually run tonight?
Complexity classes stay abstract until you divide by a machine. At roughly a billion simple operations a second, each class has an input size beyond which it stops being an option at all.
A million records squared is 1012 operations, about 1,000 seconds, or just under 17 minutes. At n = 1,000 the same code finished in a millisecond, which is why “it worked fine on my test data” is such a common line in post-mortems.
You rarely need to compute a complexity. You need to know which band your input puts you in, and whether the input can grow.
The short version
- Big O keeps the shape of growth and drops everything else.
- At small n every class looks similar; the differences explode as n grows.
- Constant factors decide the winner below the crossover, so measure at your real n.
- Divide operations by about a billion a second to see what is actually runnable.