The Analysis of Algorithms

The purpose of this book is to teach the tequniques needed to analyze algorithms. Students should have a background in computer science up through data structures and in mathematics through calculus. The text is organized by analysis techniques and includes a systematic and largely self-contained treatment of the mathematics needed for elementary and intermediate analysis, as well as brief guides to the sources for more advanced techniques. Each is illustrated by application to the analysis of a realistic algorithm. Explicit guidance for the use of various methods is provided. Exercises provide the student with the opportunity to apply the techniques in developing original algorithm analysis. 1. Introduction -- 2. Summing Series -- 3. Products And Binomials -- 4. Asymptotic Approximation -- 5. Simple Linear Recurrences -- 6. General Linear Recurrences -- 7. Full-history And Nonlinear Recurrences -- 8. Multidimensional Recurrences -- 9. Lower Bounds And Np Completeness -- 11. Statistics. Paul Walton Purdom, Jr., Cynthia A. Brown. Includes Indexes. Bibliography: P. 495-503.