Big-O: why the algorithm beats the hardware

One million items. Two ways to search them. One finishes before you blink. With the other one, you will die of old age first. Watch them race. Linear scan checks every item, one at a time. Binary search throws away half the list at every step. Twenty steps in, binary search has already found it. Linear scan has looked at twenty items out of a million. Twenty steps against a million. Same problem, same computer, same programming language. That gap is not the machine. It is the algorithm. So we stop counting seconds and start measuring growth. Constant time never moves. Logarithmic barely moves. Linear keeps pace with the input. Then quadratic, which hurts. And exponential, which leaves the screen and never comes back. And you can read it straight off the code. One loop over n is linear. Put a loop inside a loop and the work multiplies: that is quadratic. Halve the range each step and it collapses to logarithmic. One last rule. Throw the constants away. As n grows, only the biggest term is still standing. Two n plus three is just n. N squared plus a hundred n is just n squared. So pick the complexity first, and measure second. There is no point shaving milliseconds off a loop that should never have been quadratic.