Singularity analysis, Hadamard products, and tree recurrences
arXiv:math/0306225 · doi:10.1016/j.cam.2004.04.014
Abstract
We present a toolbox for extracting asymptotic information on the coefficients of combinatorial generating functions. This toolbox notably includes a treatment of the effect of Hadamard products on singularities in the context of the complex Tauberian technique known as singularity analysis. As a consequence, it becomes possible to unify the analysis of a number of divide-and-conquer algorithms, or equivalently random tree models, including several classical methods for sorting, searching, and dynamically managing equivalence relations
47 pages. Submitted for publication
References in corpus (2)
Cited by in corpus (8)
- On q-functional equations and excursion moments
- Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees
- Phase Transition in the Aldous-Shields Model of Growing Trees
- Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
- On the operations of sequences in rings and binomial type sequences
- Area limit laws for symmetry classes of staircase polygons
- Counting walks by their last erased self-avoiding polygons using sieves
- The number of optimal matchings for Euclidean Assignment on the line