The average case analysis of algorithms : Saddle Point Asymptotics - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 1994

The average case analysis of algorithms : Saddle Point Asymptotics

Philippe Flajolet
  • Function : Author
  • PersonId : 829512
Robert Sedgewick
  • Function : Author

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.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
RR-2376.pdf (1.76 Mo) Télécharger le fichier

Dates and versions

inria-00074300 , version 1 (24-05-2006)

Identifiers

  • HAL Id : inria-00074300 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More