You are here

Mathematics for the Analysis of Algorithms

D. H. Greene and D. E. Knuth
Publication Date: 
Number of Pages: 
Modern Birkhäuser Classics
[Reviewed by
Allen Stenger
, on

This is a short cookbook of methods for analyzing the run time of computer algorithms, aimed at computer scientists, and concentrating on the algorithms found in Knuth’s The Art of Computer Programming, Volume 3: Sorting and Searching. It has many things, especially about asymptotic analysis, that will interest mathematicians also. The original edition was in 1981, and it was revised lightly twice to produce this 1990 third edition.

The book’s general approach is to quote the relevant theorems, sketch the method of attack, and launch into several examples. The first 75 pages of the book is the narrative (which includes many solved examples), and the remaining 50 pages are sample exam problems (and solutions) from the teaching of this course at Stanford. One of the samples is labeled “qualifying exam” and so is presumably from the PhD qualifying exams at Stanford; the book seems aimed at PhD students rather than upper-division undergraduates or first-year graduate students.

About half of the narrative is devoted to explicit solutions (mostly of recursions, but also some binomial and hypergeometric sums) and the other half is devoted to asymptotic solutions. The first half has become less important today (particularly as a cookbook) because many of these problems can now be solved automatically by computers, but the second half is still very useful. The second half includes a lot of hard-to-find material, such as Darboux’s method of getting asymptotics of a sequence from the singularities of its generating function.

There’s a lot of overlap with two other books from the same school of research. Flajolet & Sedgewick’s Analytic Combinatorics includes full proofs and is much more thorough, but only covers generating functions. Graham & Knuth & Patashnik’s Concrete Mathematics does not go into as much depth as the present book, but covers all kinds of mathematics useful for computer science, not just for the analysis of algorithms. It is the best book for a beginner in algorithm analysis. Both books were published after the present book, so are more up to date. The difficulty of the problems tackled in the present book is much higher than in these other two books. An excellent book specifically about asymptotic analysis is de Bruijn’s Asymptotic Methods in Analysis.

Bottom line: a very erudite book, full of interesting things for both mathematicians and computer scientists, but aimed at researchers, not beginners.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.

  • Binomial identities
  • Recurrence relations
  • Operator methods
  • Asymptotic analysis
    • Basic concepts
    • Stieltjes integration and asymptotics
    • Asymptotics from generating functions
  • Midterm exam and solutions, 1980
  • Final exam and solutions, 1980
  • Midterm exam and solutions, 1982
  • Final exam and solutions, 1982
  • Midterm exam and solutions, 1988
  • Final exam and solutions, 1988
  • A qualifying exam problem and solution, 1988