On the occasion (today in the USA) of Don Knuth’s 70th birthday, several bloggers have posted tributes (see Jeffrey Shallit’s list). His list of achievements is really impressive, and he has had a big influence on me. To name a few areas, somewhat facetiously: his founding of the field of analysis of algorithms (AofA) led to the development of a community of people who are heavy users of generating function methodology and therefore may be interested in my research in that area, and it gave me something nice to teach as a mathematician moving into a CS department! More seriously, I can’t conceive of computer science as a real science without proper analysis of algorithms, and I would hate to have to write papers without using TeX.

Since unalloyed praise can get a bit cloying, I will mention that it might have been better for the world if Knuth (or someone else) had been able to build a school of AofA in the USA. The algorithms community in the USA is heavily dominated by “worst-case” analysis and indeed by analysis of problem complexity, which is a very weak form of analysis of algorithms, concentrating as it does on lower bounds and rather weak (many would say useless) upper bounds.

The main development of AofA along Knuthian lines has been in Europe, in France (Philippe Flajolet and others) and Austria particularly. In recent years Bob Sedgewick and others have tried to bridge the gap between these communities through meetings such as ANALCO, but at least to my eyes they have not yet had great success.

Of course some may say that the sort of very detailed analysis by Knuth is unnecessary for a working computer scientist. And even if his analyses made sense in the days of flat memory, the prevalence of such things as caching makes it impossible to make such detailed predictions nowadays. But perhaps we just need some better mathematics.