Two Ways to Be Right

Earlier in this unit we counted statements and named the result n, or 3n, or n squared. Here we count something smaller and more concrete: how many times one particular call happens, on a list of a size we name out loud.

That is a number you can check by hand, and it is where the difference between two correct algorithms first becomes visible.

Suppose weight(data) walks the whole list and hands back a single number. Nothing in the loop below changes data, so weight returns the same number on every pass. Computing it inside the loop means computing that same number again for every element.

Some code reads a fixed number of elements no matter how long the list is. Reading the first element costs the same on ten numbers as on ten million, because the length never enters into it.

Work like that is called constant time. It is the cheapest thing on the scale: doubling the input does not change it, and neither does multiplying it by a thousand.

Binary search invites an off-by-one worth pinning down, because two different numbers both feel like the answer.

Cutting the range in half until a single candidate is left counts the HALVINGS. But that last surviving candidate still has to be looked at before the search can answer. So the number of elements actually examined, the PROBES, is one more than the number of halvings.