The Growth Classes

Seven growth classes cover almost every algorithm a working engineer meets: constant, logarithmic, linear, n log n, quadratic, exponential and factorial. At ten items they are all instant. At a thousand, two of them are already hopeless. At a million, the quadratic one takes hours, and the last two need more time than the universe has existed.

Knowing which class a piece of code belongs to is knowing its ceiling: how far the data can grow before the code stops finishing. This topic puts numbers on each class, so that the ceiling can be read off before the data gets there.

Seven Classes at Three Sizes

Constant work is one step at every size. Logarithmic work is about 3 steps at ten items, 10 at a thousand and 20 at a million. Linear work is the size itself. Work that grows with n log n is about 33 steps at ten, ten thousand at a thousand and twenty million at a million. Quadratic work is a hundred steps at ten, a million at a thousand, and a trillion at a million.

The last two classes do not fit in a sentence at any size worth having. Two to the power n is already 1,024 at ten items, a number with 302 digits at a thousand, and one with about 301,000 digits at a million. Factorial is 3,628,800 at ten, a number with 2,568 digits at a thousand, and one with more than five million digits at a million.

Turning Counts Into Time

A step count becomes a time once you know how many steps a second the machine does. Compiled code on one core manages a billion simple steps a second or more; a tight loop over integers reaches about three billion, as Chapter 3 measures. A Python loop manages roughly thirty million. Taking a round billion for compiled code, quadratic work at a million items, a trillion steps, takes about 17 minutes of compiled code and about nine hours of Python.

Exponential work leaves those numbers behind almost immediately. Two to the fifty steps is about 13 days of compiled work. Two to the hundred is about 40 trillion years, roughly three thousand times the age of the universe. Nothing in between those two inputs looks unusual: fifty items and a hundred items are both small lists.

The Friendly Classes

Constant and logarithmic work barely notice the input: a billion items is only 30 halvings. Linear work touches everything once, and it is the price of reading the input at all, so no algorithm that needs to see all the data can beat it. Work that grows with n log n is the price of sorting and of most divide-and-conquer algorithms, and Chapter 7 shows why sorting by comparison cannot do better.

A system built only from these four classes scales with its data. When the catalogue grows tenfold, its jobs take about ten times longer, or a little more, and a capacity plan can be written with a ruler.

Quadratic, the Class That Ships

Quadratic work is the one that passes code review. It hides in comparing every pair of records to find duplicates, in a membership test on a list inside a loop, and in building a long string by adding one piece at a time. At a thousand records it takes milliseconds and nobody notices.

At 2 million records, comparing every pair is about two trillion comparisons. Hashing each record once and grouping by the hash, which Chapter 5 explains, finds the same duplicates in about 2 million steps. The answer is the same. The difference is a million to one, and it is the most common capacity failure in ordinary business code.

Comparing every pair of records to find duplicates→Group by a hash key: O(n)

Testing membership in a list inside a loop→Build a set once, then test it: O(n)

Adding strings together one piece at a time→Collect the pieces, join once: O(n)

Finding the closest pair of values→Sort, then compare neighbours: O(n log n)

Exponential and Factorial

Trying every subset of n items is 2ⁿ work, and trying every ordering is n! work. Both are correct, and both finish only for tiny n. A delivery van with 20 stops, counting the depot, has about 60 quadrillion distinct round trips, and checking them all at a billion a second takes about two years. A regular expression written carelessly can backtrack exponentially on a 30-character input and freeze a server thread, which Chapter 14 takes apart.

For some of these problems nobody knows an algorithm that is fundamentally better than trying everything. Chapter 14 explains which problems those are, and what engineers do instead: approximate, bound the input, or give up on perfection.

What the Class Costs in Production

The class sets how far a system can grow before it falls over. An O(n log n) nightly job over a catalogue ten times bigger takes a little more than ten times longer. An O(n²) job takes a hundred times longer, so the four-minute job becomes a seven-hour job. An exponential step turns one customer's slightly larger input into a worker that never returns.

The practical habit is one line of arithmetic before a design is signed off: take today's timing, multiply by what the class says tenfold data costs, and see whether the answer still fits in the night.