x PREFACE methods from classical discrete mathematics,with a primary focus on devel- oping 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 fo- cus 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 sup- ports 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 em- phasize the algorithmic material in the second half of the book.But our primary intention is that most students should be able to learn new mate- rial 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 ex- ercises,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 nu- merous opportunities for instructors to supplement lecture and reading ma- terial with computation-based laboratories and homework assignments.The material covered here is an ideal framework for students to develop exper- tise in a symbolic manipulation system such as Mathematica,MAPLE,or SAGE.More important,the experience of validating the mathematical stud- ies by comparing them against empirical studies is an opportunity to provide valuable insights for students that should not be missed. Booksite.An important feature of the book is its relationship to the booksite aofa.cs.princeton.edu.This site is freely available and contains supple- mentary material about the analysis of algorithms,including a complete set of lecture slides and links to related material,including similar sites for A/go- rithms and Analytic Combinatorics.These resources are suitable both for use by any instructor teaching the material and for self-study. www.it-ebooks.info
x P Ş ő Œ ō ŏ ő methods from classical discrete mathematics, with a primary focus on developing basic concepts and techniques. Ļey 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. Ļough 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 ŀrst part of the book, with applications drawn from Chapters 6 through 9. Another approach, more oriented towards computer science, would be to brieły 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. Ļe 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. Booksite. An important feature of the book is its relationship to the booksite aofa.cs.princeton.edu. Ļis 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. Ļese resources are suitable both for use by any instructor teaching the material and for self-study. www.it-ebooks.info
PREFACE i 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 Uni- versity,European Community(Alcom Project),Institute for Defense Anal- yses,Ministere de la Recherche et de la Technologie,Stanford University, Universite 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 teach- ers 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. www.it-ebooks.info
P Ş ő Œ ō ŏ ő xi 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. Ļis 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 inłuence 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 ŀrst edition. We would like to speciŀcally 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. www.it-ebooks.info
NOTE ON THE SECOND EDITION N March 2011,I was traveling with my wife Linda in a beautiful but some- what rmo reof the word.Carchinguth mye offline,I found the shocking news that my friend and colleague Philippe had passed away,suddenly,unexpectedly,and far too early.Unable to travel to Paris in time for the funeral,Linda and I composed a eulogy for our dear friend that I would now like to share with readers of this book. Sadly,I am writing from a distant part of the world to pay my respects to my longtime friend and colleague,Philippe Flajolet.I am very sorry not to be there in person,but I know that there will be many opportunities to bonor Pbilippe in the future and expect to be fully and personally involved on these occasions. Brilliant,creative,inquisitive,and indefatigable,yet generous and charming. Philippe's approach to life was contagious.He changed many lives,including my own.As our research papers led to a survey paper,then to a monograph,then to a book,then to two books,then to a life's work,I learned,as many students and collaborators around the world have learned,that working with Philippe was based on a genuine and beartfelt camaraderie.We met and worked together in cafes,bars,luncbrooms,and lounges all around the world.Philippe's routine was always the same.We would discuss something amusing that happened to one friend or another and then get to work.After a wink,a hearty but quick laugh, a puff of smoke,another sip of a beer,a few bites of steak frites,and a drawn out"Well..."we could proceed to solve the problem or prove the theorem.For so many of us,these moments are frozen in time. The world has lost a brilliant and productive mathematician.Philippe's un- timely passing means that many things may never be known.But bis legacy is a coterie offollowers passionately devoted to Philippe and his mathematics who will carry on.Our conferences will include a toast to him,our research will build upon his work,our papers will include the inscription"Dedicated to the memory of Philippe Flajolet,"and we will teach generations to come.Dear friend,we miss you so very much,but rest assured that your spirit will live on in our work. This second edition of our book An Introduction to the Analysis of Algorithms was prepared with these thoughts in mind.It is dedicated to the memory of Philippe Flajolet,and is intended to teach generations to come. Jamestown RI,October 2012 R.S. www.it-ebooks.info
N O T E O N T H E S E C O N D E D I T I O N I N March 2011, I was traveling with my wife Linda in a beautiful but somewhat remote area of the world. Catching up with my mail after a few days offline, I found the shocking news that my friend and colleague Philippe had passed away, suddenly, unexpectedly, and far too early. Unable to travel to Paris in time for the funeral, Linda and I composed a eulogy for our dear friend that I would now like to share with readers of this book. Sadly, I am writing from a distant part of the world to pay my respects to my longtime friend and colleague, Philippe Flajolet. I am very sorry not to be there in person, but I know that there will be many opportunities to honor Philippe in the future and expect to be fully and personally involved on these occasions. Brilliant, creative, inquisitive, and indefatigable, yet generous and charming, Philippe’s approach to life was contagious. He changed many lives, including my own. As our research papers led to a survey paper, then to a monograph, then to a book, then to two books, then to a life’s work, I learned, as many students and collaborators around the world have learned, that working with Philippe was based on a genuine and heartfelt camaraderie. We met and worked together in cafes, bars, lunchrooms, and lounges all around the world. Philippe’s routine was always the same. We would discuss something amusing that happened to one friend or another and then get to work. After a wink, a hearty but quick laugh, a puff of smoke, another sip of a beer, a few bites of steak frites, and a drawn out “Well...” we could proceed to solve the problem or prove the theorem. For so many of us, these moments are frozen in time. Ļe world has lost a brilliant and productive mathematician. Philippe’s untimely passing means that many things may never be known. But his legacy is a coterie of followers passionately devoted to Philippe and his mathematics who will carry on. Our conferences will include a toast to him, our research will build upon his work, our papers will include the inscription “Dedicated to the memory of Philippe Flajolet ,” and we will teach generations to come. Dear friend, we miss you so very much, but rest assured that your spirit will live on in our work. Ļis second edition of our book An Introduction to the Analysis of Algorithms was prepared with these thoughts in mind. It is dedicated to the memory of Philippe Flajolet, and is intended to teach generations to come. Jamestown RI, October 2012 R. S. www.it-ebooks.info
TABLE OF CONTENTS CHAPTER ONE:ANALYSIS OF ALGORITHMS 3 1.1 Why Analyze an Algorithm? 3 1.2 Theory of Algorithms 6 1.3 Analysis of Algorithms 13 1.4 Average-Case Analysis 16 1.5 Example:Analysis of Quicksort 18 1.6 Asymptotic Approximations 27 1.7 Distributions 30 1.8 Randomized Algorithms 33 CHAPTER TWO:RECURRENCE RELATIONS 41 2.1 Basic Properties 43 2.2 First-Order Recurrences 48 2.3 Nonlinear First-Order Recurrences 52 2.4 Higher-Order Recurrences 55 2.5 Methods for Solving Recurrences 61 2.6 Binary Divide-and-Conquer Recurrences and Binary 70 Numbers 2.7 General Divide-and-Conquer Recurrences 80 CHAPTER THREE:GENERATING FUNCTIONS 91 3.1 Ordinary Generating Functions 92 3.2 Exponential Generating Functions 97 3.3 Generating Function Solution of Recurrences 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-Three Recurrence 120 with OGFs 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 www.it-ebooks.info
T A B L E O F C O N T E N T S CŔōŜŠőŞ OŚő: AŚōŘťş ŕş śŒ AŘœśŞ ŕŠŔřş 3 1.1 Why Analyze an Algorithm? 3 1.2 Ļeory of Algorithms 6 1.3 Analysis of Algorithms 13 1.4 Average-Case Analysis 16 1.5 Example: Analysis of Quicksort 18 1.6 Asymptotic Approximations 27 1.7 Distributions 30 1.8 Randomized Algorithms 33 CŔōŜŠőŞ Tţś: RőŏšŞŞőŚŏő RőŘōŠ ඦş 41 2.1 Basic Properties 43 2.2 First-Order Recurrences 48 2.3 Nonlinear First-Order Recurrences 52 2.4 Higher-Order Recurrences 55 2.5 Methods for Solving Recurrences 61 2.6 Binary Divide-and-Conquer Recurrences and Binary 70 Numbers 2.7 General Divide-and-Conquer Recurrences 80 CŔōŜŠőŞ TŔŞőő: GőŚőŞōŠ ŕŚœ FšŚŏŠ ඦş 91 3.1 Ordinary Generating Functions 92 3.2 Exponential Generating Functions 97 3.3 Generating Function Solution of Recurrences 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-Ļree Recurrence 120 with OGFs 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 xv www.it-ebooks.info
xvi TABLE OF CONTENTS CHAPTER FOUR:ASYMPTOTIC APPROXIMATIONS 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8“Normal'"Examples from the Analysis of Algorithms 207 4.9“Poisson"Examples from the Analysis of Algorithms 211 CHAPTER FIVE:ANALYTIC COMBINATORICS 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 CHAPTER SIX:TREES 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 www.it-ebooks.info
xvi T ō Ŏ Ř ő ś Œ C ś Ś Š ő Ś Š ş CŔōŜŠőŞ FśšŞ: AşťřŜŠśŠ ŕŏ AŜŜŞśŤ ŕřōŠ ඦş 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8 “Normal” Examples from the Analysis of Algorithms 207 4.9 “Poisson” Examples from the Analysis of Algorithms 211 CŔōŜŠőŞ F ŕŢő: AŚōŘťŠ ŕŏ CśřŎ ŕŚōŠśŞ ŕŏş 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 CŔōŜŠőŞ S ŕŤ: TŞőőş 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 www.it-ebooks.info