Donald Knuth, The Man Who Made Algorithms Count

Donald Knuth is the reason computer science can say how expensive a program is rather than merely that it works. Before him the field had algorithms and it had intuitions about which ones were fast. He turned that into arithmetic, by counting operations exactly, and the habit he established is the single most useful tool for reading a quantum computing claim today. He is better known for other things, including a book he has been writing since 1962, a typesetting system he built because a publisher set his equations badly, a line about premature optimisation that almost everyone quotes wrongly, and cheques for $2.56. This guide covers all of it, and then makes the case that his method matters more to quantum computing than any of his individual results. Born 10 January 1938, Milwaukee, Wisconsin Education BS and simultaneous MS, Case Institute of Technology, 1960. PhD in mathematics, Caltech, 1963 Position Stanford University from the late 1960s, later Professor of The Art of Computer Programming, emeritus since 1993 Known for The Art of Computer Programming, the analysis of algorithms, TeX, literate programming Major awards Turing Award 1974, National Medal of Science 1979, Kyoto Prize 1996 Named after him Knuth-Morris-Pratt, Knuth-Bendix, Robinson-Schensted-Knuth, up-arrow notation Key takeaways Knuth turned algorithms into a quantitative science. He established that you analyse an algorithm by counting its operations exactly rather than by describing it, and that discipline is now the basis of the whole field. The Art of Computer Programming has run for more than sixty years and is unfinished. Commissioned in 1962 as a single book on programming techniques, it is now planned as seven volumes, of which five have appeared. He wrote TeX because a publisher ruined his equations. Unhappy with the typesetting of a new edition, he stopped work on his life’s project and spent years building a typesetting system instead. The premature optimisation line is almost always quoted wrongly. The full sentence protects the critical 3 per cent of code, and the paper it comes from is an argument for measuring rather than for ignoring performance. Constant factors are the part asymptotic notation throws away. That omission is exactly where quantum speedup claims tend to fail, because error correction overhead lives in the constant. His method is the best available test of a quantum claim. Ask what is counted, what the constant is, what the classical baseline is, how the data gets in, and where the crossover falls. On this page Who Donald Knuth is The book that ate a career What the analysis of algorithms means Why he counts instead of classifying Why the books use assembly language The algorithms with his name on them Sorting, searching and lower bounds The most misquoted line in computing TeX, and stopping to build a typesetter Literate programming The $2.56 cheques Giving up email in 1990 Surreal numbers, MMIX and the rest Reading Knuth today Where the method has costs Why this matters for quantum computing The crossover problem Volume 4 and the classical baseline Five questions to ask of any speedup The lineage into quantum textbooks What the method is worth Frequently asked questions Who Donald Knuth is Donald Knuth was born Donald Ervin Knuth on 10 January 1938 in Milwaukee, Wisconsin. He took a bachelor’s degree in mathematics at the Case Institute of Technology in 1960, where his undergraduate work was strong enough that the faculty awarded him a master’s degree in mathematics at the same time by special vote, then completed a doctorate in mathematics at Caltech in 1963 with a thesis on finite semifields and projective planes. He joined Stanford in 1968 and stayed. He held the Fletcher Jones chair in computer science from 1977, then for a short period at the turn of the 1990s a chair with the unusual title Professor of The Art of Computer Programming, and he took emeritus status in 1993 so that he could concentrate on writing. He received the Turing Award in 1974 at the age of 36, the National Medal of Science in 1979 and the Kyoto Prize in 1996. The bare biography understates what happened. Knuth entered a field that barely existed as an academic discipline and left it with a mathematical foundation, a canonical reference work, and a professional standard for what counts as understanding a program. The book that ate a career In 1962 a publisher asked Donald Knuth, then a graduate student, to write a book on programming techniques. He accepted, started writing, and discovered that the material he needed did not exist in any organised form. The book grew, the scope expanded, and what began as one volume became a plan for seven. One commission in 1962, five volumes so far, and more than sixty years of work. The gap between volume 3 in 1973 and volume 4A in 2011 is where TeX happened. Five volumes have appeared so far. Volume 1, Fundamental Algorithms, appeared in 1968, Volume 2, Seminumerical Algorithms, followed in 1969, and Volume 3, Sorting and Searching, in 1973. Then came a gap of nearly four decades before Volume 4A, Combinatorial Algorithms, Part 1, arrived in 2011, with Volume 4B, Combinatorial Algorithms, Part 2, in 2022. The work has not stopped since. In February 2025 Knuth published Volume 4, Fascicle 7, Constraint Satisfaction, a 304-page instalment he describes as the first third of Volume 4C, which is how the later material is reaching readers while the full volumes are assembled. The delay has an explanation, covered further down, and it is one of the more remarkable digressions in the history of the field. The important point about The Art of Computer Programming is not its length but its method. Knuth does not describe algorithms in prose and move on. He states them precisely, proves what they do, and calculates how many operations they take on inputs of a given size. What the analysis of algorithms means The phrase analysis of algorithms is now a standard course title, and Knuth is the person who made it a subject. The idea is that an algorithm is a mathematical object with measurable properties, and that the useful property is cost as a function of input size. Before this became routine, comparisons were largely empirical or intuitive. You ran two programs and saw which finished first, which tells you about your machine and your test data rather than about the algorithms. Knuth’s approach was to count the operations an algorithm performs, as an exact function of the input, using the mathematics of generating functions, recurrences and asymptotics. The consequence is that statements about algorithms became provable rather than anecdotal. You can say that one method requires a specific number of comparisons on average, that another has a worst case that cannot be improved, and that a third is optimal because no algorithm of its kind can do better. That last kind of statement, a lower bound, is where the field gets its hardest results, and it is exactly the form Grover’s optimality proof takes in quantum computing. Why he counts instead of classifying Donald Knuth is associated with big-O notation, which he did much to standardise for describing growth rates. He is also unusually insistent that big-O is not the end of the analysis, and this is the part of his practice most relevant to quantum computing. Asymptotic notation deliberately discards constant factors. An algorithm taking 1000n steps and one taking 2n steps are both linear, and by that classification they are equivalent. On any actual computer one of them is five hundred times slower, and no amount of asymptotic reasoning will tell you that. The asymptotically better algorithm is the flatter line, and it loses on every input to the left of the crossover. Where that crossover sits is a question about constants, which asymptotic notation cannot answer. So Knuth counts. His books give operation counts with the constants attached, often to a precision that readers find eccentric, and the reason is that the constants decide which program to run. An algorithm with a better growth rate and a punishing constant is a worse algorithm for every input smaller than the crossover point, and for many real problems that crossover sits beyond any input anyone will ever supply. Why the books are written in assembly language One decision by Donald Knuth in The Art of Computer Programming reliably annoys new readers. The programs are not written in a familiar high-level language but in assembly code for a machine Knuth invented, called MIX, which he is in the course of replacing with a more modern design named MMIX. The reasoning follows from the project’s purpose. If the goal is to count operations exactly, you need to know what an operation costs, and a high-level language hides that behind a compiler whose behaviour changes between versions and vendors. An idealised machine with a published instruction timing gives a stable unit of account, so a claim about an algorithm’s cost stays true regardless of what hardware exists. The choice has a price. Readers must learn an artificial assembly language before they can follow the code, which has kept the books off many reading lists. Knuth’s answer is that the alternative costs more, because an analysis expressed in a language that hides the machine is an analysis of the compiler rather than of the algorithm. The argument is directly familiar to anyone working on quantum resource estimation. Counting gates in an abstract circuit model is the quantum equivalent of counting MIX instructions, and the reason both are done is the same. You need a unit that does not shift when the hardware does. The algorithms with his name on them Several results carry his name, and they span a wider range than one field usually allows. The Knuth-Morris-Pratt algorithm searches for a pattern within a text in time proportional to the combined length of both, by exploiting the structure of the pattern to avoid re-examining characters. It is the string search taught in nearly every algorithms course. The Knuth-Bendix completion algorithm belongs to symbolic algebra and automated reasoning, turning a set of equations into a system that can decide whether two expressions are equivalent. The Robinson-Schensted-Knuth correspondence is a piece of combinatorics linking permutations to pairs of tableaux, and it appears in representation theory far from anything Knuth was originally studying. Knuth’s up-arrow notation is a way of writing numbers too large for ordinary notation, extending exponentiation the way exponentiation extends multiplication. Algorithm X is the name he gave to the straightforward backtracking method for exact cover problems, which he described as a statement of the obvious trial-and-error approach. What is his is the dancing links implementation of it, an elegant use of doubly linked lists that made the method fast enough for constraint puzzles including Sudoku solvers. Sorting and searching, and knowing when to stop Volume 3 is the most read of the series, and it demonstrates the method better than any summary can. Sorting looks like a solved problem until you look closely, at which point it becomes a study in trade-offs between comparisons, memory movement, cache behaviour and the structure of the data you happen to have. The volume does not simply recommend a sorting algorithm. It establishes that comparison-based sorting cannot beat a certain number of comparisons in the worst case, which is a lower bound and therefore a permanent fact rather than a current best. It then works through the practical methods and shows precisely where each one wins, which depends on input size, on how nearly sorted the data already is, and on what the machine’s memory hierarchy costs. That combination of a proved lower bound plus honest accounting of the constants is the template for the whole discipline. It is also, incidentally, the exact shape of the strongest result in quantum search. Grover’s algorithm is optimal in the same sense that comparison sorting has a floor, and in both cases the useful engineering question begins after the optimality proof rather than ending with it. The most misquoted line in computing Donald Knuth wrote the sentence that programmers quote most and read least. It comes from a paper called Structured Programming with go to Statements, published in Computing Surveys in December 1974, in the middle of a technical argument about control flow. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. The half most people quote stops before the word yet. Read whole, the sentence is not an instruction to ignore performance. It says that most code does not matter, that some code matters enormously, and that the job is to find out which is which before you start tuning. That is an argument for measurement, made by a man who spent his career measuring. The misreading has consequences beyond etiquette. Treating the quote as permission to defer all performance thinking produces systems whose slowness is architectural and cannot be tuned away later. Knuth’s actual position is the opposite, which is that you should know where the cost is, and you can only know that by counting. TeX, and stopping to build a typesetter In the spring of 1977 the second edition of Volume 2 came back set by a new photographic process, and Knuth thought the mathematics looked terrible. His response was not to complain to the publisher. He stopped writing The Art of Computer Programming and set out to build a typesetting system that would render mathematics properly. The result was TeX, together with METAFONT for designing the typefaces it would use. He expected the detour to take a matter of months. It took years, and TeX became the standard for mathematical and scientific publishing, which it remains. Nearly every physics and computer science paper you read, including essentially all quantum computing preprints on arXiv, is set in TeX or a descendant of it. The episode says something about how Knuth works. Faced with a tool that was not good enough for the job, he treated building the tool as part of the job. The cost was roughly a decade of the book he considers his life’s work. Literate programming Out of the TeX effort came another idea. Knuth argued that programs should be written to be read by people, with the explanation and the code interleaved in whatever order best suits a human reader, and that the machine-readable version should be extracted from that document rather than the other way round. He built systems called WEB and later CWEB to do this, and wrote TeX itself in that style, publishing the entire source as a book. The practice never became mainstream, though its influence is visible in tools that mix narrative and executable code, including the computational notebooks now standard in scientific computing and in quantum software development. The $2.56 cheques Donald Knuth offers a reward to anyone who finds an error in his books. The amount is $2.56, on the grounds that 256 pennies make one hexadecimal dollar, with smaller sums for suggestions that are valuable rather than corrections. The cheques became collectors’ items, and recipients frequently framed them rather than banking them. After problems with cheque fraud he stopped issuing paper cheques in 2008 and now sends certificates of deposit drawn on a fictitious institution he calls the Bank of San Serriffe. The joke is a typographic one, and it has outlasted several real banks. Underneath the whimsy is a serious position about correctness. Knuth is publicly committed to the claim that his books are right, in a way that costs him money when they are not, and the bounty makes every reader a proofreader with an incentive. Giving up email in 1990 Donald Knuth stopped using email more than three decades ago and has been explicit about why. His own account is worth quoting because it explains the working method behind the books. I have been a happy man ever since January 1, 1990, when I no longer had an email address. His stated reasoning is that email suits people whose role is to be on top of things, and that his own role is the opposite. As he puts it, his job is “to be on the bottom of things”, work that “takes long hours of studying and uninterruptible concentration”. Correspondence still reaches him, printed by an assistant and handled in batches, with a stated goal of dealing with it “in batch mode” roughly one day every six months. It is easy to read this as eccentricity and harder to argue with the output. The judgement embedded in it is that depth on one problem is worth more than responsiveness across many, which is an unusual position for a modern researcher to hold and an unusually well tested one. Surreal numbers, MMIX and the rest Knuth’s output does not stop at the main series. In 1974 he published Surreal Numbers, a short book that introduces John Conway’s number system through a fictional dialogue between two people on a beach, and which coined the name the system now carries. Concrete Mathematics, written with Ronald Graham and Oren Patashnik and published in 1989, grew out of a Stanford course and teaches the mathematical technique needed for algorithm analysis. MMIX is a hypothetical computer he designed to replace the older machine used in the earlier volumes, so that the programs in the books will run on an architecture resembling something modern, though the published volumes still use MIX and the changeover is a work in progress. He has also written on typography, on music and on religion, publishing 3:16 Bible Texts Illuminated in 1990. Reading Knuth today The Donald Knuth series is a reference rather than a course, and treating it as something to read cover to cover is the usual mistake. Each volume is organised so that a section can be entered directly, with the mathematical preliminaries collected early in Volume 1 and the exercises graded by difficulty from trivial warm-ups to open research problems. For most readers the practical route is to use it as an authority rather than a tutorial. When you need to know what is actually known about a specific algorithm, including which variants exist and what their exact costs are, the answer is usually there and usually more complete than anywhere else. Concrete Mathematics is the better starting point for the underlying technique, since it was built from a taught course and assumes less. The exercise grading deserves a note of its own. Knuth marks problems on a scale that includes items he knows to be unsolved, so a reader who cannot finish one may have wandered into open research rather than missed something. Several exercises have been solved by readers over the years, which is a form of collaboration few textbooks manage. Where the method has costs An honest profile of Donald Knuth has to record what the approach has cost, and the most obvious item is the books themselves. Five volumes in more than sixty years is not a pace that serves readers who need the material now, and the sections on subjects that moved quickly were dated by the time they appeared. Knuth’s insistence on completeness and correctness is the reason for both the quality and the delay. The artificial assembly language has kept the series from being widely taught, whatever its merits as an analytical device. Literate programming, which he considered one of his more important contributions, never achieved general adoption, and the tooling around it remained specialised. TeX is a genuine success and also famously difficult to extend, which is why the ecosystem around it grew into layers of macro packages rather than a redesign. There is a broader criticism worth stating, which is that exhaustive analysis suits stable problems better than fast-moving ones. A field changing every few years cannot wait for a definitive account, and much of modern software engineering is concerned with problems where the constants are dominated by systems behaviour that no clean analysis captures. Knuth’s method is the right tool for a specific and important class of question, not for every question. Why this matters for quantum computing Nothing in the preceding sections on Donald Knuth is about quantum computing, and no claim is made here that Knuth has taken a public position on it. The connection is methodological, and it is stronger than any opinion would be. Quantum computing is a field where the central commercial question is whether a speedup is real. That question is not a physics question. It is an algorithm analysis question of exactly the kind Knuth spent sixty years teaching people to ask, and the field’s most damaging errors have all been failures of that discipline rather than failures of physics. Consider the pattern. A quantum algorithm is proved to need fewer queries to an oracle than any classical algorithm, and the result is reported as a speedup for a real problem. That step is invalid, because a query bound is a statement about a black box and a running time is a statement about gates. Knuth’s first question of any claim is what precisely is being counted, and it disposes of a great deal of overstatement on its own. The crossover problem The constant factor issue is where the connection becomes sharp. Grover’s search algorithm delivers a quadratic improvement, needing about the square root of N steps where a classical scan needs N, and the result is provably optimal. Then you count the steps properly. Each quantum step is a full error-corrected operation, which on current designs means thousands of physical operations across hundreds or thousands of physical qubits per logical qubit. Each classical step is a single memory read. The quantum algorithm has the better growth rate and a constant factor several orders of magnitude worse, which puts the crossover at a problem size that may not be reachable. This is precisely the situation his chart describes, and it is why quantum advantage arguments that stop at the asymptotics are incomplete. The honest version of a Grover claim states where the crossover falls and whether a machine of that size is plausible. Very few marketing claims do. The same discipline has produced the field’s best recent work.

When Craig Gidney cut the estimated cost of factoring RSA-2048 from 20 million noisy qubits in eight hours to under a million noisy qubits in under a week, the saving came not from a single breakthrough but from combining approximate residue arithmetic, yoked surface codes and magic state cultivation. That is Knuth’s method applied to quantum hardware, and it moved the field further than most experimental results of the same period. Volume 4 and the classical baseline There is a more direct link, and it sits in the volumes Knuth is writing now. Volume 4 covers combinatorial algorithms, meaning satisfiability, exact cover, constraint problems and the rest of the territory that optimisation lives in. That is the same territory quantum optimisation proposals target. Algorithms such as QAOA and quantum annealing are pitched at scheduling, routing and graph problems, and the case for them depends entirely on how good the best classical method is. Volume 4 is, among other things, a careful account of exactly how good those classical methods are, including modern satisfiability solvers that routinely handle instances once considered hopeless. Anyone assessing a quantum optimisation claim needs that baseline, because the failure mode is comparing against a weak classical algorithm rather than the best one. This is the same error that dequantization exposed in quantum machine learning, where claimed exponential advantages disappeared once someone wrote the better classical version. Five questions to ask of any speedup The practical value of Knuth’s method can be reduced to a short list. None of these questions require quantum expertise, and together they filter most of what is wrong with public claims in the field. None of these are quantum questions. They are the standard questions of algorithm analysis, and they are the fastest way to read a quantum claim honestly. Question What a weak claim looks like What a strong claim looks like What is counted? Queries to an oracle, presented as running time Gate counts, with the oracle’s own cost included What is the constant? Asymptotics only, constants unmentioned Explicit operation counts including error correction overhead What is the baseline? A textbook classical method The best known classical algorithm, tuned How does data get in? Assumes the dataset is already in superposition Accounts for loading, or avoids needing it Where is the crossover? Not stated A problem size, with a view on whether that machine can exist The lineage into quantum textbooks You can see Donald Knuth’s influence in how quantum computing is written about, even where nobody cites him. The standard reference in the field, Nielsen and Chuang, presents quantum algorithms in exactly the form he established, which is a precise statement of the procedure, a proof of what it computes, and an accounting of the resources it consumes. That structure is not inevitable. A field could describe its algorithms informally and compare them experimentally, and quantum computing did some of that in its early years, which is part of why several claims from that period did not survive scrutiny. The move toward stating gate counts, circuit depths and qubit requirements as explicit functions of problem size is the field adopting the analytical standard that classical computing settled on decades earlier. The current work on fault-tolerant resource estimation is the clearest example. Papers now report Toffoli counts, magic state consumption and physical qubit totals for specific problem instances, with the constants attached rather than hidden. That is a mature analytical culture, and it arrived in quantum computing about fifty years after Knuth established it for classical algorithms. What the method is worth Donald Knuth’s reputation rests on a book he has not finished, a typesetting system he built as a digression, and a sentence about optimisation that is quoted backwards. The durable contribution is less visible and much larger, which is the idea that a claim about an algorithm should be a calculation rather than an assertion. Quantum computing needs that idea more than most fields, because its claims are hard to check by intuition and its hardware does not yet exist at the scale the claims assume. The results that have most improved the field’s honesty in the past decade have all been analysis results rather than experiments. Dequantization removed speedups that were never there, and careful resource estimation replaced hand-waving about millions of qubits with numbers that can be argued about. There is a final point that matters for anyone deciding whether to take the field seriously. A discipline that can measure itself can also correct itself, and quantum computing has now done so publicly more than once, withdrawing speedups that did not hold and revising resource estimates by orders of magnitude in both directions. That is a sign of health rather than of trouble, and it is only possible because there is an agreed way to count. Both are Knuth’s discipline at work. He would probably say he was only counting. The biographical details here are taken from Knuth’s own curriculum vitae and from the volume history on his Art of Computer Programming pages. The optimisation sentence comes from Structured Programming with go to Statements, in Computing Surveys for December 1974. Frequently asked questions Who is Donald Knuth? Donald Knuth is an American computer scientist, born in 1938, best known for writing The Art of Computer Programming and for founding the analysis of algorithms as a mathematical discipline. He is Professor Emeritus at Stanford and received the Turing Award in 1974. What is The Art of Computer Programming? It is a multi-volume reference work on algorithms that Knuth was commissioned to write in 1962 and is still writing. Five volumes have appeared, in 1968, 1969, 1973, 2011 and 2022, and seven are planned.

Did Donald Knuth invent big-O notation? No. The notation predates him and comes from mathematics, though he did a great deal to standardise its use for describing algorithm running times. He is also insistent that asymptotic notation alone is insufficient, since it discards the constant factors that decide which algorithm is actually faster. What did Knuth actually say about premature optimisation? The full sentence, from a 1974 paper, is that we should forget about small efficiencies about 97 per cent of the time because premature optimisation is the root of all evil, yet should not pass up our opportunities in that critical 3 per cent. It is an argument for measuring where the cost is, not for ignoring performance. Why did Knuth create TeX? He was unhappy with the typographic quality of a new edition of one of his volumes, particularly the mathematics. He paused work on The Art of Computer Programming to build a typesetting system that would set equations properly, and TeX became the standard for scientific publishing. Why does Donald Knuth not use email? He gave up his email address on 1 January 1990, on the grounds that email suits people whose role is to stay on top of things while his own work requires long periods of uninterrupted concentration. Correspondence is printed for him and handled in batches. What is the $2.56 cheque? It is the reward Knuth offers for finding an error in his books, set at $2.56 because 256 pennies make one hexadecimal dollar. He stopped sending paper cheques in 2008 after cheque fraud and now issues certificates of deposit at a fictitious Bank of San Serriffe. What is literate programming? It is Knuth’s idea that a program should be written as a document for human readers, with explanation and code interleaved in whatever order makes the logic clearest, and the compilable source extracted from that document automatically. He built the WEB and CWEB systems for it and wrote TeX itself that way. Has Knuth finished The Art of Computer Programming? No. Seven volumes are planned and five have been published, the most recent full volume being Volume 4B in 2022. He has continued working on the remaining material, publishing sections as fascicles first, most recently Volume 4 Fascicle 7 on constraint satisfaction in February 2025. How is Knuth relevant to quantum computing? Through method rather than through any quantum work of his own. The central question in quantum computing, whether a claimed speedup is real, is an algorithm analysis question, and the discipline Knuth established of counting operations exactly, identifying the true classical baseline and locating the crossover point is the most reliable way to answer it. Read next Quantum algorithms Quantum advantage Quantum machine learning What is quantum computing Quantum supremacy Stay currentSee today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals. Tags: