What Big-O Actually Measures (and What It Doesn't)

Imagine looking up a name in a phone book two different ways: flipping through page by page from the front, versus jumping to the roughly right section because you know it's alphabetized, then narrowing down from there. Both methods work. But double the size of the phone book, and the page-by-page method roughly doubles your worst-case effort, while the alphabetized-jump method barely changes at all. Big-O notation is the formal way of describing that difference — not the exact time either method takes, but how the effort grows as the input grows.

Written as O(something), Big-O describes a growth pattern, not a speed. O(1) means the effort stays the same no matter how big the input gets — looking up a specific page number you already know. O(log n) means the effort grows very slowly, like the alphabetized phone-book search — each step in this pattern eliminates a large chunk of what's left to check, similar to how a binary search cuts a sorted list in half each time. O(n) means the effort grows in direct proportion to the input's size — checking every entry in an unsorted list, one at a time. O(n²) means the effort grows with the square of the input size — a common cost when an algorithm compares every item to every other item.

The first thing Big-O doesn't measure is actual wall-clock speed. An O(n²) algorithm on a small input can easily run faster in practice than an O(n log n) algorithm on the same input, because Big-O ignores constant factors — the fixed overhead a particular implementation carries regardless of input size. Big-O only describes what happens as the input grows large enough for that growth pattern to dominate everything else; it says nothing about which of two algorithms wins on the actual, real-world input sizes a specific program will ever see.

The second thing Big-O doesn't measure, by default, is typical or average performance — it usually describes the worst case, the most punishing input an algorithm could possibly be handed. An algorithm can be fast on almost every real input and still carry an intimidating worst-case Big-O rating driven by a rare, pathological input that almost never occurs in practice. Quicksort, covered in this site's sorting-algorithms article, is the textbook example: excellent average performance, but a worst-case rating that looks much worse on paper than it behaves in almost every real use.

None of this makes Big-O useless — quite the opposite. It's the right tool for exactly one question: will this approach still be workable if the input grows from a hundred items to a hundred million? For that question, growth pattern is precisely what matters, and everything Big-O deliberately leaves out — constant factors, typical-case behavior, actual runtime on today's hardware — is exactly the kind of detail that would make the answer stop generalizing across different machines, implementations, and input sizes in the first place.