Skip to Main content Skip to Navigation
New interface
Reports (Research report)

The average case analysis of algorithms : Saddle Point Asymptotics

Philippe Flajolet 1 Robert Sedgewick 
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This report is part of a series whose aim is to present in a synthetic way the major methods of ``analytic combinatorics'' needed in the average--case analysis of algorithms. It reviews the use of the saddle point method in order to estimate asymptotically coefficients of fast growing generating functions. The applications treated concern the enumeration of set partitions and integer partitions, permutations with cycle restrictions, increasing subsequences, as well as distribution estimates when large powers are involved.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:00:34 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:07 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 4:26:34 PM


  • HAL Id : inria-00074300, version 1



Philippe Flajolet, Robert Sedgewick. The average case analysis of algorithms : Saddle Point Asymptotics. [Research Report] RR-2376, INRIA. 1994. ⟨inria-00074300⟩



Record views


Files downloads