P-5.1 Measuring Cost, and What Big-O Hides

What this is and why it exists

Growth-rate notation is the common language for comparing algorithms. It is also routinely over-trusted.

It discards constants. It ignores small inputs. It says nothing at all about memory or cache behaviour. Any one of those can decide a real contest between two working implementations.

So learn both halves. Derive it confidently, and remember what it left out. A decision anyone should act on needs both.

The vocabulary

• Input size — the number the cost is expressed in terms of, usually called n.
• Growth rate — how the cost rises as the input grows.
• Constant factor — the multiplier the notation deliberately drops.
• Worst case — the most expensive input of that size.
• Average case — the expected cost over some assumed distribution of inputs.
• In place — using no significant memory beyond the input itself.

The mental model

Start by counting. Ask how many times the innermost work happens when the input has size n. Nested loops multiply. Sequential loops add. That accounting is the whole technique, and most people who find this hard have never actually done it slowly once.

Then learn the ladder, in order: constant, logarithmic, linear, linear times logarithmic, quadratic, exponential. Nearly everything sits on one of those rungs. Knowing which rung tells you something concrete — what input size becomes impossible. Quadratic is fine at a thousand and hopeless at a million. Exponential is hopeless at forty.

Next, be precise about which question you are answering. Worst, average and best case are three different questions and the answers differ. Quicksort is quadratic at worst and fast in practice. Hash lookup is constant on average and linear at worst. Stating which case you mean is part of stating the result, and leaving it out is how people end up surprised.

Now, what the notation throws away, which is the part usually skipped. Two algorithms with the same growth rate can differ tenfold in real time, because constants were discarded. For small inputs the algorithm with the worse rate frequently wins. That is why real sorting libraries fall back to a quadratic sort below a threshold. And memory use and cache behaviour do not appear anywhere in the notation at all.

So finish by measuring. Time two implementations across a range of input sizes and plot it. Where measurement disagrees with the analysis, that disagreement is the interesting finding, not an embarrassment. It means something real is happening that your model does not contain, and finding out what is how you learn.

What you should now be able to explain or do

Derive the growth rate of a piece of code by counting the innermost work. Name the common rates in order and say what input size each makes impossible. Distinguish worst, average and best case, and say which one you mean. Name the three things the notation discards. Measure two implementations across a range of sizes and interpret a disagreement with the analysis.

Check yourself