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.
Type de document :
Rapport
[Research Report] RR-2376, INRIA. 1994
Liste complète des métadonnées

https://hal.inria.fr/inria-00074300
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:00:34
Dernière modification le : samedi 17 septembre 2016 - 01:35:21
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:26:34

Fichiers

Identifiants

  • HAL Id : inria-00074300, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

70