Singularity analysis, Hadamard products, and tree recurrences

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

Nevin Kapur, Philippe Flajolet, James Allen Fill

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 productsGenerating functionsAsymptotic expansionsGeneralized polylogarithmShape functionalSingularity analysisDivide-and-conquerContour integrationMoment pumpingTree recurrences

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Asymptotic enumeration (05A16) Inversion theorems (40E99)

Related Items

On the operations of sequences in rings and binomial type sequences ⋮ Reductions in binary search trees ⋮ Stochastic analysis of the extra clustering model for animal grouping ⋮ Phase transition in a generalized Eden growth model on a tree ⋮ The left-right-imbalance of binary search trees ⋮ Counting walks by their last erased self-avoiding polygons using sieves ⋮ Limiting distributions for the number of inversions in labelled tree families ⋮ Generating Functions and the Solutions of Full History Recurrence Equations ⋮ Fluctuations of balanced urns with infinitely many colours ⋮ Central Limit Theorems for Additive Tree Parameters with Small Toll Functions ⋮ Diagonal Asymptotics for Products of Combinatorial Classes ⋮ Analysis of a drop-push model for percolation and coagulation ⋮ Hadamard grade of power series ⋮ Asymptotic enumeration of RNA structures with pseudoknots ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ A distributional study of the path edge-covering numbers for random trees ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ The number of optimal matchings for Euclidean assignment on the line ⋮ Area Limit Laws for Symmetry Classes of Staircase Polygons ⋮ Central and local limit theorems for RNA structures ⋮ On \(q\)-functional equations and excursion moments ⋮ Statistics of canonical RNA pseudoknot structures ⋮ Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees ⋮ A central limit theorem for additive functionals of increasing trees ⋮ Stacks in canonical RNA pseudoknot structures ⋮ Limit Distributions and Scaling Functions ⋮ The sum of powers of subtree sizes for conditioned Galton-Watson trees

Cites Work

• 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
• 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