The Problem with Big O

Time complexity analysis, often called Big O—“O” as in “on the Order of”—is a kind of simplified, back-of-the-envelope differential calculus taught to computer science students. Students are given the impression that Big O can predict how fast code runs, and many of them cling to this mistaken belief late into their careers. (Big O/Ω/Θ notation is also used to represent space complexity, but if you ask a CS grad the Big O of some algorithm, they invariably give you time, not space.)

For example, students are taught that the relative speed of different algorithms depends mainly on how many arithmetic operations they do. In reality, hardware cache misses are often the bottleneck, because they have a high constant factor: They are many times more expensive than arithmetic operations.

A similar McGuffin is the Big O complexity of collecting data into containers. The conventional wisdom is that node-based data structures like linked lists support faster insertions than flat data structures like vectors (aka arrays). The truth is that you cannot know until you profile. Here’s a video of ACM Fellow, IEEE Fellow, Faraday Medal winner, etc., etc., Bjarne Stroustrup showing vectors blow the doors off linked lists: Why you should avoid Linked Lists. The bigger the collection, the greater the vector’s advantage—regardless of where elements are inserted—which is exactly the opposite of what CS students are taught. (By the way, Bubble Sort has excellent performance on mostly-sorted input. Maybe we should do a whole series on Lies My CS Professor Told Me.)

Big O lets us state a theoretical limit on how some deterministic quantity might change in relation to other numbers. For example, “linear complexity” means that doubling the size of one thing will no more than double the size of another. It doesn’t tell us whether the quantity is in any way related to real-world performance though, and we as human beings are shockingly bad at identifying what will correlate. The math is technically correct, but Big O is only reliable for numbers that can be derived through pure logic, not necessarily numbers that matter in the physical world. Some CS students are even taught to disdain metrics like “stopwatch time” that are hard to predict, yet critically important in real-world engineering.

Rich Hickey, creator of the Clojure programming language, sums the point up nicely:

As soon as it’s running on a computer, it’s not math anymore. It’s running on a computer, it’s consuming memory, it’s consuming clock cycles. It’s observably doing something over time.

In this InfoQ interview, Hickey addresses Big O directly:

You can say “OK, technically it’s O(log N), but if it’s never more than three hops from my huge data structure, maybe I don’t care anymore about that.” In other words, constant factors matter.

Big O, by definition, drops constant factors. It plays a fundamental role in computer science, but that’s not the same thing as software engineering. For engineering projects—even very large ones—math is no substitute for data.