Analysis of Algorithms is a thorough overview of the primary techniques used in the mathematical analysis of algorithms. Drawing from classical mathematical topics (discrete mathematics, elementary real analysis, and combinatorics) and classical computer science topics (algorithms and data structures), it

• • • Can serve as a textbook for a course in discrete mathematics for computer scientists.
    • Is suitable for introducing computer science to students in mathematics.
    • Provides access to literature in the field, particularly Knuth’s books and Flajolet’s papers.
    • Emphasizes analysis as a basis for a scientific approach to evaluating performance.

Coverage includes recurrence relations, generating functions, asymptotics, and analytic combinatorics, with applications to algorithms and combinatorial structures such as trees, permutations, strings and tries, words, and mappings.

Chapter One. Analysis of Algorithms

1.1 Why Analyze an Algorithm?
1.2 Theory of Algorithms
1.3 Analysis of Algorithms
1.4 Average-Case Analysis
1.5 Example: Analysis of Quicksort
1.6 Asymptotic Approximations
1.7 Distributions
1.8 Randomized Algorithms

Chapter Two. Recurrence Relations

2.1 Basic Properties
2.2 First-Order Recurrences
2.3 Nonlinear First-Order Recurrences
2.4 Higher-Order Recurrences
2.5 Methods for Solving Recurrences
2.6 Binary D-and-C Recurrences and Binary Numbers
2.7 General Divide-and-Conquer Recurrences

Chapter Three. Generating Functions 

3.1 Ordinary GFs
3.2 Exponential GFs
3.3 GF Solution of Recurrences
3.4 Expanding GFs
3.5 Transformations with GFs
3.6 Functional Equations on GFs
3.7 Solving the Quicksort Median-of-3 Recurrence
3.8 Counting with GFs
3.9 Probability GFs
3.10 Bivariate GFs
3.11 Special Functions

Chapter Four. Asymptotic Approximations

4.1 Notation for Asymptotic Approximations
4.2 Asymptotic Expansions
4.3 Manipulating Asymptotic Expansions
4.4 Asymptotic Approximations of Finite Sums
4.5 Euler-Maclaurin Summation
4.6 Bivariate Asymptotics
4.7 Laplace Method
4.8 “Normal” Examples from Analysis of Algorithms
4.9 “Poisson” Examples from Analysis of Algorithms

Chapter Five. Analytic Combinatorics

5.1 Formal Basis
5.2 Symbolic Method for Unlabelled Classes
5.3 Symbolic Method for Labelled Classes
5.4 Symbolic Method for Parameters
5.5 Generating Function Coefficient Asymptotics

Chapter Six. Trees

6.1 Binary Trees
6.2 Forests and Trees
6.3 Combinatorial Equivalences
6.4 Properties of Trees
6.5 Examples of Tree Algorithms
6.6 Binary Search Trees
6.7 Average Path Length in Catalan Trees
6.8 Path Length in Binary Search Trees
6.9 Additive Parameters of Random Trees
6.10 Height
6.11 Average-Case Results on Properties of Trees
6.12 Lagrange Inversion
6.13 Rooted Unordered Trees
6.14 Labelled Trees
6.15 Other Types of Trees

Chapter Seven. Permutations

7.1 Basic Properties of Permutations
7.2 Algorithms on Permutations
7.3 Representations of Permutations
7.4 Enumeration Problems
7.5 Analyzing Properties of Permutations
7.6 Inversions and Insertion Sorts
7.7 Left-to-Right Minima and Selection Sort
7.8 Cycles and In Situ Permutation
7.9 Extremal Parameters

Chapter Eight. Strings and Tries

8.1 String Searching
8.2 Combinatorial Properties of Bitstrings
8.3 Regular Expressions
8.4 FSAs and the Knuth-Morris-Pratt Algorithm
8.5 Context-Free Grammars
8.6 Tries
8.7 Trie Algorithms
8.8 Combinatorial Properties of Tries
8.9 Larger Alphabets

Chapter Nine. Words and Mappings

9.1 Hashing with Separate Chaining
9.2 Balls-and-Urns Model and Properties of Words
9.3 Birthday Paradox and Coupon Collector Problem
9.4 Occupancy Restrictions and Extremal Parameters
9.5 Occupancy Distributions
9.6 Open Addressing Hashing
9.7 Mappings
9.8 Integer Factorization and Mappings

This book is intended to be a thorough overview of the primary techniques used in the mathematical analysis of algorithms. The material covered draws from classical mathematical topics, including discrete mathematics, elementary real analysis, and combinatorics, as well as from classical computer science topics, including algorithms and data structures. The focus is on “average-case” or “probabilistic” analysis, though the basic mathematical tools required for “worst-case” or “complexity” analysis are covered as well.
     We assume that the reader has some familiarity with basic concepts in both computer science and real analysis. In a nutshell, the reader should be able to both write programs and prove theorems. Otherwise, the book is intended to be self-contained.
     The book is meant to be used as a textbook in an upper-level course on analysis of algorithms. It can also be used in a course in discrete mathematics for computer scientists, since it covers basic techniques in discrete mathematics as well as combinatorics and basic properties of important discrete structures within a familiar context for computer science students. It is traditional to have somewhat broader coverage in such courses, but many instructors may find the approach here to be a useful way to engage students in a substantial portion of the material. The book also can be used to introduce students in mathematics and applied mathematics to principles from computer science related to algorithms and data structures.
     Despite the large amount of literature on the mathematical analysis of algorithms, basic information on methods and models in widespread use has not been directly accessible to students and researchers in the field. This book aims to address this situation, bringing together a body of material intended to provide readers with both an appreciation for the challenges of the field and the background needed to learn the advanced tools being developed to meet these challenges. Supplemented by papers from the literature, the book can serve as the basis for an introductory graduate course on the analysis of algorithms, or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this field.

Preparation. Mathematical maturity equivalent to one or two years’ study at the college level is assumed. Basic courses in combinatorics and discrete mathematics may provide useful background (and may overlap with some material in the book), as would courses in real analysis, numerical methods, or elementary number theory. We draw on all of these areas, but summarize the necessary material here, with reference to standard texts for people who want more information.
     Programming experience equivalent to one or two semesters’ study at the college level, including elementary data structures, is assumed. We do not dwell on programming and implementation issues, but algorithms and data structures are the central object of our studies. Again, our treatment is complete in the sense that we summarize basic information, with reference to standard texts and primary sources.

Related books. Related texts include The Art of Computer Programming by Knuth; Algorithms, Fourth Edition, by Sedgewick and Wayne; Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein; and our own Analytic Combinatorics. This book could be considered supplementary to each of these.
     In spirit, this book is closest to the pioneering books by Knuth. Our focus is on mathematical techniques of analysis, though, whereas Knuth’s books are broad and encyclopedic in scope, with properties of algorithms playing a primary role and methods of analysis a secondary role, this book can serve as basic preparation for the advanced results covered and referred to in Knuth’s books. We also cover approaches and results in the analysis of algorithms that have been developed since publication of Knuth’s books.
     We also strive to keep the focus on covering algorithms of fundamental importance and interest, such as those described in Sedgewick’s Algorithms (now in its fourth edition, coauthored by K. Wayne). That book surveys classic algorithms for sorting and searching, and for processing graphs and strings. Our emphasis is on mathematics needed to support scientific studies that can serve as the basis of predicting performance of such algorithms and for comparing different algorithms on the basis of performance.
     Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms has emerged as the standard textbook that provides access to the research literature on algorithm design. The book (and related literature) focuses on design and the theory of algorithms, usually on the basis of worst-case performance bounds. In this book, we complement this approach by focusing on the analysis of algorithms, especially on techniques that can be used as the basis for scientific studies (as opposed to theoretical studies). Chapter 1 is devoted entirely to developing this context.
     This book also lays the groundwork for our Analytic Combinatorics, a general treatment that places the material here in a broader perspective and develops advanced methods and models that can serve as the basis for new research, not only in the analysis of algorithms but also in combinatorics and scientific applications more broadly. A higher level of mathematical maturity is assumed for that volume, perhaps at the senior or beginning graduate student level. Of course, careful study of this book is adequate preparation. It certainly has been our goal to make it sufficiently interesting that some readers will be inspired to tackle more advanced material!

How to use this book. Readers of this book are likely to have rather diverse backgrounds in discrete mathematics and computer science. With this in mind, it is useful to be aware of the implicit structure of the book: nine chapters in all, an introductory chapter followed by four chapters emphasizing mathematical methods, then four chapters emphasizing combinatorial structures with applications in the analysis of algorithms, as follows:

INTRODUCTION

1. ANALYSIS OF ALGORITHMS

DISCRETE MATHEMATICAL METHODS

2. RECURRENCE RELATIONS
3. GENERATING FUNCTIONS
4. ASYMPTOTIC APPROXIMATIONS
5. ANALYTIC COMBINATORICS

ALGORITHMS AND COMBINATORIAL STRUCTURES

6. TREES
7. PERMUTATIONS
8. STRINGS AND TRIES
9. WORDS AND MAPPINGS

Chapter 1 puts the material in the book into perspective, and will help all readers understand the basic objectives of the book and the role of the remaining chapters in meeting those objectives. Chapters 2 through 4 cover methods from classical discrete mathematics, with a primary focus on developing basic concepts and techniques. They set the stage for Chapter 5, which is pivotal, as it covers analytic combinatorics, a calculus for the study of large discrete structures that has emerged from these classical methods to help solve the modern problems that now face researchers because of the emergence of computers and computational models. Chapters 6 through 9 move the focus back toward computer science, as they cover properties of combinatorial structures, their relationships to fundamental algorithms, and analytic results.
     Though the book is intended to be self-contained, this structure supports differences in emphasis when teaching the material, depending on the background and experience of students and instructor. One approach, more mathematically oriented, would be to emphasize the theorems and proofs in the first part of the book, with applications drawn from Chapters 6 through 9. Another approach, more oriented towards computer science, would be to briefly cover the major mathematical tools in Chapters 2 through 5 and emphasize the algorithmic material in the second half of the book. But our primary intention is that most students should be able to learn new material from both mathematics and computer science in an interesting context by working carefully all the way through the book.
     Supplementing the text are lists of references and several hundred exercises, to encourage readers to examine original sources and to consider the material in the text in more depth.
     Our experience in teaching this material has shown that there are numerous opportunities for instructors to supplement lecture and reading material with computation-based laboratories and homework assignments. The material covered here is an ideal framework for students to develop expertise in a symbolic manipulation system such as Mathematica, MAPLE, or SAGE. More important, the experience of validating the mathematical studies by comparing them against empirical studies is an opportunity to provide valuable insights for students that should not be missed.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online. These lectures are fully coordinated with the text, but also include examples and other materials that supplement the text and are intended to bring the subject to life. As with traditional live lectures, their purpose is to inform and inspire, motivating students to study and learn from the text. Our experience is that student engagement with the material is significantly better with videos than with live lectures because of the ability to play the lectures at a chosen speed and to replay and review the lectures at any time.

Booksite. Another important feature of the book is its relationship to our Analysis of Algorithms website, which we refer to as the booksite. This site is freely available and contains supplementary material about the analysis of algorithms, including a complete set of lecture slides and links to related material, including similar sites for Algorithms and Analytic Combinatorics. These resources are suitable both for use by any instructor teaching the material and for self-study.

Acknowledgments. We are very grateful to INRIA, Princeton University, and the National Science Foundation, which provided the primary support for us to work on this book. Other support has been provided by Brown University, European Community (Alcom Project), Institute for Defense Analyses, Ministère de la Recherche et de la Technologie, Stanford University, Université Libre de Bruxelles, and Xerox Palo Alto Research Center. This book has been many years in the making, so a comprehensive list of people and organizations that have contributed support would be prohibitively long, and we apologize for any omissions.

Don Knuth’s influence on our work has been extremely important, as is obvious from the text.

Students in Princeton, Paris, and Providence provided helpful feedback in courses taught from this material over the years, and students and teachers all over the world provided feedback on the first edition. We would like to specifically thank Philippe Dumas, Mordecai Golin, Helmut Prodinger, Michele Soria, Mark Daniel Ward, and Mark Wilson for their help.

Corfu, September 1995     Ph. F. and R. S.
Paris, December 2012                       R. S.

An extensive amount of content associated with this book is available online, most of it freely available. The introduction to the COURSES page and the essay on online learning on this website tell the full story of the types of content, relationships, and how it may best be used by students and teachers of all sorts. The COURSES page for this book gives specific details. Here are some brief descriptions and quick links to this material.

Booksite. Our Analysis of Algorithms website contains hundreds of files, fully coordinated with our textbook and also useful as a standalone resource. It consists of the following elements:

Excerpts. A condensed version of the text narrative, for reference while online.
Exercises. Selected exercises from the book and “web exercises” developed since its publication, along with solutions to selected exercises.
Assignments. Creative assignments that we have used at Princeton.

This is a living resource that is constantly being improved and updated.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online via the CUbits platform. This platform applies modern machine-learning models to build searchable transcripts, indexing, and other features that enhance the experience of learning from the videos.

Lecture slides. The lectures are based on hundreds of detailed, carefully prepared slides that are useful for reviewing the lecture content. These are available at the websites just listed, and on the COURSES page for this book, which provides a convenient interface for browsing through them.

MOOC. The Coursera course Analysis of Algorithms is a massive open online course based on the lecture videos that includes exercises, auto-assessed programming assignments, and other features encouraging coordinated study of the material in the book.

Princeton course. You can find details on how we conduct our course at Princeton on our course website. Our students watch lectures online and complete weekly programming assignments. We ensure loose synchronization via the book site and regular e-mail for authoritative communication from faculty to students.