Looking up a name in a phone book by flipping to the middle, deciding whether your name is before or after that page, and repeating in whichever half remains, finds any entry among a million names in about twenty comparisons. Reading the phone book front to back until you happen to hit the right name could take up to a million comparisons for the unluckiest name. Both are legitimate ways to search a sorted list. The gap between twenty and a million isn't a minor implementation detail — it's the entire reason some software feels instant at any scale and other software quietly stops working the moment real users show up.
What the notation is actually measuring
Big-O notation describes how an algorithm's running time grows as the size of its input, usually called n, grows — not the exact number of seconds it takes on one particular machine, but the shape of the curve as n gets large. An algorithm that's O(n) does roughly proportional work to its input size: double the input, expect roughly double the time. An algorithm that's O(n²) does work proportional to the input size squared: double the input, and the time roughly quadruples, because doubling n means the n² term is now four times as large. An algorithm that's O(log n) — like the phone-book halving search, binary search — barely notices growth at all: doubling the input adds only one more halving step, so going from a million entries to two million costs one extra comparison, not twice the comparisons.
These growth rates aren't close to each other, and the gap between them is invisible on small inputs precisely because small numbers don't have room to show a difference — ten items sorted by a good algorithm and a bad one both finish so fast neither difference is noticeable. The same two algorithms on ten million items can differ by a factor that makes one option finish before you notice and the other one still running an hour later.
Why engineers argue about the exponent, not the code
A huge amount of algorithm design is exactly this: finding a way to do a task in O(n log n) instead of O(n²), or O(log n) instead of O(n), because the growth rate — not clever line-by-line optimisation of a single implementation — is what decides whether a system survives its data growing by a factor of a thousand. Efficient sorting algorithms like mergesort run in O(n log n); a naive sort that compares every pair of elements runs in O(n²); both produce a correctly sorted list, and only one of them is still usable once the list has a million entries in it rather than a hundred.
What we're still unsure about
Big-O deliberately throws away information that can matter enormously in practice: constant factors and lower-order terms. An algorithm that's technically O(n) but does an enormous, fixed amount of setup work before it starts can be slower in the real world, for realistic input sizes, than an O(n log n) algorithm with a tiny constant factor — Big-O only guarantees which one wins eventually, as n keeps growing, not which one wins on the actual dataset sitting in front of an engineer today. Treating a better Big-O class as an automatic proof of better real-world performance is a common and genuinely costly mistake, not a subtlety this post can wave away.
This sits inside Big-O Notation & Complexity Analysis, one of eight topics in Algorithms, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.