Singularity analysis, Hadamard products, and tree recurrences

DOI10.1016/j.cam.2004.04.014zbMath1056.05011arXivmath/0306225MaRDI QIDQ1765441

James Allen Fill, Philippe Flajolet, Nevin Kapur

Publication date: 23 February 2005

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0306225

zbMATH Keywords

Hadamard products; Generating functions; Asymptotic expansions; Generalized polylogarithm; Shape functional; Singularity analysis; Divide-and-conquer; Contour integration; Moment pumping; Tree recurrences

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05A16: Asymptotic enumeration

40E99: Inversion theorems

Related Items

Central Limit Theorems for Additive Tree Parameters with Small Toll Functions, Diagonal Asymptotics for Products of Combinatorial Classes, Stochastic analysis of the extra clustering model for animal grouping, Analysis of a drop-push model for percolation and coagulation, Hadamard grade of power series, Limiting distributions for additive functionals on Catalan trees, Phase transition in a generalized Eden growth model on a tree, The left-right-imbalance of binary search trees, Asymptotic enumeration of RNA structures with pseudoknots, On \(q\)-functional equations and excursion moments, Stacks in canonical RNA pseudoknot structures, Limiting distributions for the number of inversions in labelled tree families, Reductions in binary search trees, A distributional study of the path edge-covering numbers for random trees, Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees, Area Limit Laws for Symmetry Classes of Staircase Polygons, Generating Functions and the Solutions of Full History Recurrence Equations, Limit Distributions and Scaling Functions

Cites Work

• Limiting distributions for additive functionals on Catalan trees
• The Brownian excursion area: A numerical analysis
• Page usage in a quadtree index
• The expected linearity of a simple equivalence algorithm
• On the analysis of linear probing hashing
• Singularity analysis and asymptotics of Bernoulli sums
• Analytic variations on quadtrees
• Mellin transforms and asymptotics. The mergesort recurrence
• Random walks, heat equation and distributed algorithms
• Normal convergence problem? Two moments and a recurrence may be the clues
• On binary search tree recursions with monomials as toll functions
• On the Lambert \(w\) function
• Special issue: Average-case analysis of algorithms
• The contraction method for recursive algorithms
• On a probability problem connected with railway traffic
• Phase changes in randomm-ary search trees and generalized quicksort
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Singularity Analysis of Generating Functions
• A complexity calculus for recursive tree algorithms
• A Recurrence Related to Trees
• Generalized Digital Trees and Their Difference—Differential Equations
• On the Altitude of Nodes in Random Trees
• Phase transition in a random fragmentation problem with applications to computer science
• An improved master theorem for divide-and-conquer recurrences
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Partial match retrieval of multidimensional data
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• A Watson Sum for a Cubic Lattice
• 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