A First Taste of Algorithms

Interlude: The Other Exponential

✦ ✦ ✦

Between Chapters 5 and 6. No problems; ten minutes; one rumor, corrected.

You have heard, all your life, that computers got fast. The rumor is true and even understated: for half a century, the number of transistors that fit on a chip doubled roughly every two years — Moore’s law, the most famous exponential in the world — and machines rode the curve from filling rooms to fitting in pockets. (The honest footnote: the ride has been slowing. Chips stopped getting faster in the simple clock-speed sense around 2005, and even the transistor doubling has labored in recent years. Exponentials in the physical world are always a phase, never a law.)

Here is the half of the story the rumor leaves out. Over the same decades, for problem after problem, the algorithms got faster too — and where anyone has carefully measured both, the ideas have often beaten the hardware.

The best-documented case concerns linear programming — the workhorse optimization method behind airline schedules, factory plans, and shipping routes. Robert Bixby, who spent a career building the leading solvers, ran the comparison directly: take the same problems, and ask how much of the speedup between the late 1980s and the early 2000s came from better machines and how much from better mathematics. His answer, for that fifteen-year window: machines contributed a factor in the thousands — and algorithms contributed a factor in the tens of thousands. The same planning problem that ran overnight in 1990 runs in seconds today, and most of the difference is not silicon. It is people refusing, more and more skillfully, to do most of the work.

You do not have to take Bixby’s word for it, because you have already measured the other exponential yourself, in Lab 1, on your own machine. Searching a million-item list: a million steps the obvious way, twenty steps the sorted way. That is a factor of fifty thousand — from an idea, costing zero transistors, discovered before electronic computers existed. Every chapter so far has handed you another such factor. The notebook of Chapter 4 turned twenty-five billion calls into fifty. The ripple of Chapter 5 routes a continent. None of these speedups will ever flatten the way Moore’s law is flattening, because they were never physical to begin with. A proof does not decay.

So when someone gestures at a data center and says “look how fast computers got,” you may now silently append the correction: look how fast the refusals accumulated. The machines made the dumb thing quick; the chapters made most of the dumb thing unnecessary; the world you live in is the product of the two factors, and the larger factor is the quieter one.

One more thing, and then back to work. The other exponential has no fab, no supply chain, no minimum age. Its entire manufacturing base is people who have learned to ask the two questions and to count honestly — which, five chapters in, includes you. The curve runs through the reader. Chapter 6 resumes with a toll booth this book has owed you since page one, and with something rarer than a fast algorithm: a proof that no one, ever, with any idea, will beat a certain price. Even the other exponential has walls — and knowing exactly where they stand is the most valuable knowledge in the subject.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses