Automatic average-case analysis of algorithms

DOI10.1016/0304-3975(91)90145-RzbMath0768.68041MaRDI QIDQ1174718

Philippe Flajolet, Paul Zimmermann, Bruno Salvy

Publication date: 25 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

generating functioncountingcomplex analysisaverage-case complexityasymptotic estimationsLambda- Upsilon-Omega

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15)

Related Items (27)

The binomial transform and the analysis of skip lists ⋮ A calculus for the random generation of labelled combinatorial structures ⋮ Riordan arrays and combinatorial sums ⋮ Random walks, heat equation and distributed algorithms ⋮ Function composition and automatic average case analysis ⋮ Random and uniform generation of words ⋮ Analytic methods in asymptotic enumeration ⋮ Largest component in random combinatorial structures ⋮ Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation ⋮ Lower bounds for a subexponential optimization algorithm ⋮ Attribute grammars and automatic complexity analysis ⋮ The binomial transform and its application to the analysis of skip lists ⋮ Computing error bounds for asymptotic expansions of regular P-recursive sequences ⋮ Enumeration of decomposable combinatorial structures with restricted patterns ⋮ Amortized complexity verified ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ Automatic Analysis of Expected Termination Time for Population Protocols ⋮ General combinatorial schemas: Gaussian limit distributions and exponential tails ⋮ Effective bounds for P-recursive sequences ⋮ Analytic analysis of algorithms ⋮ Sorting Algorithms in MOQA ⋮ Primary decomposition of lattice basis ideals ⋮ Maximum likelihood analysis of algorithms and data structures ⋮ \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis ⋮ Symbolic asymptotics: Multiseries of inverse functions ⋮ On the robustness of interconnections in random graphs: a symbolic approach. ⋮ Relax, but don't be too lazy

Uses Software

• Maple
• ACE

Cites Work

• Gaussian limiting distributions for the number of components in combinatorial structures
• Asymptotic expansions for the coefficients of analytic generating functions
• A note on the number of functional digraphs
• The Brownian excursion area: A numerical analysis
• Resurrecting the asymptotics of linear recurrences
• Analytic models and ambiguity of context-free languages
• A logical approach to asymptotic combinatorics I. First order properties
• Some methods for computing component distribution probabilities in relational structures
• Enumeration of injective partial transformations
• Differentiably finite power series
• Recognizable formal power series on trees
• Une théorie combinatoire des séries formelles
• A trivial algorithm whose analysis isn't
• Central and local limit theorems for the coefficients of polynomials of binomial type
• Complexity analysis of term-rewriting systems
• Algebraic languages and polyominoes enumeration
• Asymptotic expansions for the coefficients of analytic functions
• Central and local limit theorems applied to asymptotic enumeration
• Optimization of LR(k) parsers
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Uniform Random Generation of Strings in a Context-Free Language
• A Generalisation of Stirling's Formula.
• Singularity Analysis of Generating Functions
• Automating program analysis
• A complexity calculus for recursive tree algorithms
• A limiting distribution for quicksort
• A unifying look at data structures
• Computer-assisted microanalysis of programs
• Mechanical program analysis
• On the Altitude of Nodes in Random Trees
• Combinatorial analysis of quicksort algorithm
• Speeding up the computations on an elliptic curve using addition-subtraction chains
• Algebraic simplification
• The Asymptotic Behaviour of the Laurent Coefficients
• [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
• AN EXAMPLE IN THE THEORY OF THE SPECTRUM OF A FUNCTION
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Automatic average-case analysis of algorithms