These pages are out of date and kept for archival. The site has moved to

Pages maintained by
Philippe Flajolet, Rocquencourt,
Helmut Prodinger, Johannesburg

[ Research | Problems | Bulletin board | People | Resources ]

[ European Base | North American Mirror ]

Analysis of Algorithms (AofA) is a field in computer science whose overall goal is an understanding of the complexity of algorithms. While an extremely large amount of research is devoted to worst-case evaluations, the focus in these pages is methods for average-case and probabilistic analysis. Properties of random strings, permutations, trees, and graphs are thus essential ingredients in the analysis of algorithms.

The subject was founded by Knuth (who coined the term "analysis of algorithms" in the mid-sixties) and is well illustrated by his monumental series, The Art of Computer Programming The field entertains close ties with a number of areas like discrete mathematics, combinatorial analysis, probability theory, analytic number theory, asymptotic analysis, complexity theory, and sometimes statistical physics.


These pages are the initiative of a bunch of people who gathered at a meeting specifically devoted to AofA, in Dagstuhl, Germany, in July 1997. This site is open to all! It is our objective that the pages become a forum for everyone with research interests in average-case and probabilistic analysis of algorithms.

Images and icons on this page are clickable.


This is for research papers, announcements of technical reports, preprints, and new results relative to Analysis of Algorithms that are available on the web. The list is now moderated by Micha Hofri.


A list of open (?) problems with comments and perhaps solutions. Don't hesitate to contribute... We're starting this column with problems presented by the Dagstuhl gang in July 1997. They are relative to Quickselect, adaptive searching, Quicksort, etc.

Bulletin board

A place where you can freely express yourself. Messages are simply archived here automatically and nobody's mailbox is encumbered.


Here, you'll find mail and home page addresses of the founders and friends of the Analysis of Algorithms pages. Also how to join. (Don't be shy!)


Some pages that we enjoy and that you might well enjoy, too! What about finding whether your newly discovered sequence 0,1,1,2,3,5,8,13,21, etc, is truly original? Is the constant 1.20205690315959428 expressible in terms of classical quantities? How do I compute directly the billionth bit of pi? Also, books and journals that are relevant.

Email and Links,

For links to these pages, please use

Selected as member of the Britannica Internet Guide.

Illustrations. Al Khwarizmi (from the History of Mathematics server); the monkey saddle that appears in the analysis of connectivity in random graphs (source: Algorithms Project); a picture of Schloss Dagstuhl (courtesy of Maurice van Keulen)