Selected Papers on Analysis of Algorithms

by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 2000), xvi+621 pp.
(CSLI Lecture Notes, no. 102.)
ISBN 1-57586-212-3
Printings made after 2006 have xvi+622 pp., because the index has gotten longer.

This is the fourth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography.) The Analysis of Algorithms volume is characterized by the following remarks quoted from its preface.

``People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.''
I once had the pleasure of writing those words for the Foreword of An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet, and I can't think of any better way to introduce the present book. After enjoying such double happiness for nearly forty years, I'm delighted that I can finally bring together this collection of essays about the subject that I love most.
... Most of the chapters in this book appeared originally as research papers that solved basic problems related to some particular algorithm or class of algorithms. But the emphasis throughout is on techniques that are of general interest, techniques that should lead also to the solution of tomorrow's problems. The way a problem is solved is generally much more important than the solution itself, and I have therefore tried to explain the principles of solution and discovery as well as I could. Thus I believe the material in this book remains highly relevant even though much of it was written many years ago. I have also appended additional material to most of the chapters, explaining subsequent developments and giving pointers to more recent literature.
... The process of compiling this book has given me an incentive to improve some of the original wording, to make all of the notations consistent with The Art of Computer Programming, to doublecheck almost all of the mathematical formulas and the reasoning that supports them, to correct all known errors, to improve the original illustrations by redrawing them with MetaPost, and to match the bibliographic information with original sources in the library. Thus the articles now appear in a form that I hope will remain useful for at least another generation or two of scholars who will carry the work forward.

This book isn't exactly ``Analysis of Algorithms for Dummies,'' but it does contain expositions of nearly every important aspect of the subject. It has the following chapters:

  1. Mathematical Analysis of Algorithms [P46]
  2. The Dangers of Computer Science Theory [P56]
  3. The Analysis of Algorithms [P44]
  4. Big Omicron and Big Omega and Big Theta [Q43]
  5. Optimal Measurement Points for Program Frequency Counts [P60]
  6. Estimating the Efficiency of Backtrack Programs [P69]
  7. Ordered Hash Tables [P64]
  8. Activity in an Interleaved Memory [P74]
  9. An Analysis of Alpha-Beta Pruning [P70]
  10. Notes on Generalized Dedekind Sums [P75]
  11. The Distribution of Continued Fraction Approximations [P106]
  12. Evaluation of Porter's Constant [P86]
  13. Analysis of the Subtractive Algorithm for Greatest Common Divisors [P76]
  14. Length of Strings for a Merge Sort [P12]
  15. The Average Height of Planted Plane Trees [P51]
  16. The Toilet Paper Problem [P111]
  17. An Analysis of Optimum Caching [P104]
  18. A Trivial Algorithm Whose Analysis Isn't [P84]
  19. Deletions That Preserve Randomness [P89]
  20. Analysis of a Simple Factorization Algorithm [P78]
  21. The Expected Linearity of a Simple Equivalence Algorithm [P88]
  22. Textbook Examples of Recursion [P135]
  23. An Exact Analysis of Stable Allocation [P149]
  24. Stable Husbands [P127]
  25. Shellsort With Three Increments [P157]
  26. The Average Time for Carry Propagation [P90]
  27. Linear Probing and Graphs [P158]
  28. A Terminological Proposal [Q33]
  29. Postscript About NP-hard Problems [Q36]
  30. An Experiment in Optimal Sorting [P52]
  31. Duality in Addition Chains [Q58]
  32. Complexity Results for Bandwidth Minimization [P77]
  33. The Problem of Compatible Representatives [P132]
  34. The Complexity of Nonuniform Random Number Generation [P80]

(Numbers like P158 and Q33 in this list refer to the corresponding papers in my list of publications.)

This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).

The papers in this book are a collection of gems that were previously published or presented as lectures by the author. The very title bears Knuth's signature, since it was he who introduced the phrase ``analysis of algorithms.'' ... He presents new ``pure'' results, which is surprising in view of the age of the topics. Generally, nobody will have the last word, as most of the papers include a sizable supplement discussing more recent developments. ... This collection will be highly prized by Knuth fans---in fact, by all computer scientists.
--Harvey Cohn, in Computing Reviews (July 2000)
The range of topics, although mostly confined to the analysis of algorithms, is vast. ... To focus on any one aspect ... would give short-shrift to the others. I therefore decided to focus this review on why I believe every reader of SIGACT News should buy this book. ... The evolution of current technology and fundamental unifying ideas can be found ... excellent reading for a beginning student in algorithm analysis ... many hilarious misapplications of theory to practice ... Knuth does an amazing job of relating how he approaches problems rather than merely recording a highly polished solution which to the reader seems to come out of the blue ... It's just plain fun to read.
--Timothy H. McNicholl, in SIGACT News (March 2001)
... combines succinctness and formal rigour with clarity and humour ... These papers on algorithmic analysis exemplify how best to convey the often complex mathematics lying behind the behaviour of apparently simple techniques. ... this collection will be of interest to those who value the highest quality technical writing, as well as to algorithm analyzers.
--Greg Michaelson, in The Computer Bulletin (May 2001)
... In summary, the papers collected here give a beautiful picture of charms and challenges of the (average-case) analysis of algorithms by the pen of its creator.
--Joachim von zur Gathen, in IEEE Annals of the History of Computing (April--June 2002)
... The particular value of this book is that much of the material has appeared in publications which are available only with difficulty. The collection is a valuable addition to the literature.
--A. D. Booth, in Mathematical Reviews (2001)
... thoughtful, thorough, and inspiring. ... Most of these papers, although excellent in every sense of this word, are quite technical, and I certainly don't recommend them for ``easy reading.'' ... I would whole-heartedly recommend this book to my colleagues who have some time to spare, and who would like to get into one of the greatest minds in computer science.
--Zhizhang Shen, in Zentralblatt Math (March 2001)


As usual, I promise to pay a reward of $2.56 to the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.

The printing of 2012 corrected all of the previously known errors in the original printing of 2000 and errors in the printing of 2008; the following further corrections are still needed. An asterisk (*) marks technical errors that are not merely typographical:

*page 64, line 5 from the bottom
change 'nonnegative' to 'positive'
*page 65, line 11
change 'perfect:' to 'perfect, if we assume that all costs at terminal nodes are positive:'
page 472, new copy
Nicholas Pippenger [“Analysis of carry propagation in addition: An elementary approach,” Journal of Algorithms 42 (2002), 317--333] has explained how to obtain these results without using contour integration.
page 603, line 7
change 'cofficients' to 'coefficients'
page 626, right column, in the entry for Nicholas John Pippenger
change '501' to '472, 501'

I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA. In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.

I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Don Knuth's home page

Don Knuth's other books

Valid HTML 4.01 Transitional