O-notation considered harmful (use Analytic Combinatorics instead)

O-notation considered harmful (use Analytic Combinatorics instead)

Big O is for theoretical limits. It is not how you compare algorithms in practice, and it is not how you classify them.

I have been skeptical of the classic “Theory of Algorithms” for a long time — of Big O, of Θ, of Ω, and of the way software engineers actually use them. They are useful for theoretical lower and upper bounds. They are often not useful for comparing performance in practice. They are often not even useful for classifying algorithms.

There is a better way. Analytic combinatorics. I wrote that in February 2013 and left it a draft. The argument did not expire.

I have had to argue this as an interviewee, and I have had to argue it on teams. In the first case it is the difference between impressing the interviewer and missing the job because the person across the table treats a sticker as a measurement. In the second it is months or years of implementation, or a financial failure, on the back of a classification that does not predict what the machine does.

The sticker

O-notation answers a theoretical question: how does this grow, in the limit, as a bound. That is a real question. It is not the question “which of these two will be faster on the inputs we actually have,” and it is not the question “what kind of algorithm is this, for the purpose of picking one.”

Engineers use it for both. Interviewers use it for both. Then they are surprised when the machine disagrees.

Quicksort vs Mergesort

The usual example. Quicksort is classified quadratic, O(n²). Mergesort is classified log-linear, O(n log n). Therefore Mergesort. In practice Quicksort is often about twice as fast, and far more space-efficient, on the inputs people actually sort. That is not a secret. It is the typical case, the cache, the data movement. Most engineers I know will still argue for Mergesort, because the sticker said so.

Robert Sedgewick has had that argument thrown at him for decades, and he is the expert. In the lecture he puts it on a slide: O-notation considered dangerous. Cannot use it to predict performance. Then the Q&A that is the picture at the top of this post:

Q: O(N log N) surely beats O(N²)? RS: Not by the definition. O expresses upper bound. Q: So, use Theta. RS: Still (typically) bounding the worst case. Is the input a worst case? Q: (whispers to colleague) I’d use the Θ(N log N) algorithm, wouldn’t you?

They still pick the sticker. He says, of the people who insist: they usually don’t program much, and they shouldn’t be recommending what practitioners do.

There are many more examples where practice and O-notation come apart. A full classical analysis of the actual running time also takes too long to be useful most of the time. So what else is there.

Analytic combinatorics

A science for this, not a slogan. Generating functions as the object of study. Specify the structure; transfer theorems give you the counts and the asymptotics, including the constants, including average case, including the effect of the input you actually have. Random generation of the structures you specified. A calculus, not a bumper sticker.

Philippe Flajolet and Robert Sedgewick spent thirty years on it. The book is Analytic Combinatorics, Cambridge, 2009. Flajolet’s line: if you can specify it, you can analyze it. It is based on the scientific method. It classifies algorithms correctly because it is measuring them, not bounding a ghost of the worst case.

For an introduction by the same authors: An Introduction to the Analysis of Algorithms. Knuth wrote the foreword:

[Sedgewick and Flajolet] are not only worldwide leaders of the field, they also are masters of exposition. I am sure that every serious computer scientist will find this book rewarding in many ways.

Sedgewick’s Coursera course Analysis of Algorithms is the lecture the slide comes from. The books are free as PDFs from INRIA and Princeton.

In 2013 I called it emerging. In 2019 the American Mathematical Society gave Analytic Combinatorics the Steele Prize for Mathematical Exposition. The interviews did not change. The sticker is still the sticker. That is the harm.

Use analytic combinatorics.

References