Why Not Just Time Them?

Before we get to asymptotic analysis, let’s look at a different way to measure how an algorithm performs. It is simple: run the algorithm and time it. If we want to compare two algorithms, we run and time them both, and the one that finishes first is the faster one. To compare linear and binary search for instance, we give each one the same array, start a timer, let it run, and record how long it took.

We can do that, and people do it. Measuring how long a program takes to run is a real technique called profiling. When you want to know whether a program is fast enough on the hardware it will actually run on, or to find which part of a large system is the slow one, profiling is the right tool. But for the question we are asking, which of these algorithms scales better, timing has a problem.

The number you get from profiling is about this run: this machine, these conditions, this input. If you run the same code on a faster processor, it finishes sooner. If the machine is busy running other programs at the time, it takes longer. The number also changes if you rewrite the code in a faster language, or compile it with a compiler that optimizes better. And the input matters too. We already talked about best vs. worst case; those are extremes of the input space, and for profiling you may want to try a variety of inputs to get a more complete picture. So the number is not just about the algorithm. It is about the whole system.

Even if you held all externals the same (the same machine, the same language, the same input), a timing still only tells you about the one input size you tried. The difference between linear and binary search, for instance, shows up as the input grows. We want to know how an algorithm behaves as the input gets larger and larger: a million elements, then a billion, then more.

Timing answers the question “how long did this take, here, on this input?” It does not answer the question we are asking, which is how the algorithm behaves as the input grows. For that we need a measure that leaves out the machine, the language, and the particular input, and tells us about the algorithm itself. That is what asymptotic analysis does.