How Fast the Work Grows

Suppose two people write programs to do the same job and one is faster on your data. That tells you almost nothing, because the relevant question is not how long it takes. It is what happens when the data gets bigger.

Say a method takes a number of steps proportional to the size of the input. Double the input, double the time. That is linear, and it is the comfortable case.

Sorting a list carefully takes a number of steps proportional to n times the logarithm of n. Double the input and the time slightly more than doubles. Still comfortable, and for any realistic amount of data, fine.

Now consider checking every possible arrangement of n items. That takes n factorial steps. Ten items give about three and a half million arrangements. Fifteen give about a thousand billion. Twenty give more than two billion billion. Each additional item multiplies the work rather than adding to it, and this is the case that cannot be rescued.

That last point deserves to be stated carefully, because it is the one people refuse to believe. Buy a computer a hundred times faster and, on a method whose cost roughly multiplies with each new item, you can handle two or three more items. Not a hundred times more. A hundred times the hardware buys you a rounding error on the problem size, and the next decade of hardware improvement buys you another one.

This is why the standard notation describes growth and throws away constant factors. It looks careless and it is deliberate. Making a program twice as fast on every input is a real and valuable piece of work, and it leaves the growth curve exactly where it was. Those are two different kinds of improvement, and the notation exists to talk about the second kind.

Polynomial time is the conventional dividing line: cost growing like a fixed power of the input size counts as tractable, and anything growing faster counts as not. The line is a convention rather than a theorem, chosen in the 1960s, and it has held up for a simple reason. Polynomial cost survives a change of machine, a change of programming language and a reasonable increase in problem size. Exponential cost survives none of them.

Now the honest caveat, which the enthusiasts for this material routinely drop.

Constants are not nothing. An algorithm with better growth and an enormous constant factor can lose on every input that anybody will ever actually have. This is not hypothetical: several matrix multiplication algorithms with better theoretical growth than the methods in use are never used, because the input size at which they would start winning is larger than any matrix anyone multiplies.

So growth analysis tells you who wins eventually, and measurement tells you who wins at your size, and serious work needs both numbers. The people who have only one of them are easy to spot by which mistake they make: either they ship something that falls over when the data grows, or they spend a month on an asymptotic improvement that nobody can observe.

The portable version of this lesson is a single habit. When somebody tells you how fast their method is, ask what happens when the input doubles.