1990 · 74 citations · 0 references
Natural SciencesMathematicsAlgorithmsNumber TheoryStatisticsAlgorithm AnalysisAnalytic Number TheoryCombinatorial Number TheoryGenerating FunctionsNumber-theoretic AlgorithmsNumerical AnalysisAnalytic ApproximationsAsymptotic AnalysisAsymptotic Analysis Of AlgorithmsAsymptotic ExpansionsAsymptotic PropertiesAverage-case AnalysisCoefficient AsymptoticsEstimation Of Sums
This report is a contributed chapter to the Handbook of Theoretical Computer Science (North-Holland, 1990). Its aim is to describe the main mathematical methods and applications in the average-case analysis of algorithms and data structures. It comprises two parts: First, we present basic combinatorial enumerations based on symbolic methods and asymptotic methods with emphasis on complex analysis techniques (such as singularity analysis, saddle point, Mellin transforms). Next, we show how to apply these general methods to the analysis of sorting, searching, tree data structures, hashing, and dynamic algorithms. The emphasis is on algorithms for which exact "analytic models" can be derived.