HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Analytic analysis of algorithms

Philippe Flajolet 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis permit to express directly the counting generating functions of wide classes of combinatorial structures. Asymptotic methods based on complex analysis permit to extract directly coefficients of structurally complicated generating functions without a need for explicit coefficient expansions. Three major groups of problems relative to algebraic equations, differential equations and iteration are presented. The range of applications includes formal languages, tree enumerations, comparison-based searching and sorting, digital structures, hashing and occupancy problems. These analytic approaches allow an abstract discussion of asymptotic properties of combinatorial structures and schemas while opening the way for automatic analysis of whole classes of combinatorial algorithms.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:56:15 PM
Last modification on : Thursday, February 3, 2022 - 11:18:12 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 5:49:16 PM


  • HAL Id : inria-00074916, version 1



Philippe Flajolet. Analytic analysis of algorithms. [Research Report] RR-1644, INRIA. 1992. ⟨inria-00074916⟩



Record views


Files downloads