A complexity calculus for recursive tree algorithms

DOI10.1007/BF01704918zbMath0658.68049MaRDI QIDQ3806812

Jean-Marc Steyaert, Philippe Flajolet

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

generating functionssingularitiesrecursive tree algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Theory of software (68N99)

Related Items (11)

On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations ⋮ Simplifications of Uniform Expressions Specified by Systems ⋮ Algebraic simplification in computer algebra: an analysis of bottom-up algorithms ⋮ Automatic average-case analysis of algorithms ⋮ Average-case analysis of pattern-matching in trees under the BST probability model ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ Unnamed Item ⋮ Analytic analysis of algorithms ⋮ Complexity analysis of term-rewriting systems ⋮ On sets of integers with prescribed gaps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Periodic oscillations of coefficients of power series that satisfy functional equations
• Recognizable formal power series on trees
• The average height of binary trees and other simple trees
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Patterns and pattern-matching in trees: An analysis
• A unifying look at data structures
• Mechanical program analysis
• Verifying Program Performance
• On the Altitude of Nodes in Random Trees

This page was built for publication: A complexity calculus for recursive tree algorithms