Singularity analysis, Hadamard products, and tree recurrences

Preprint

13 June 2003

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.math/0306225

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

Keywords

ASYMPTOTIC INFORMATION
EXTRACTING ASYMPTOTIC
SINGULARITY ANALYSIS
HADAMARD PRODUCTS
TREE RECURRENCES
ALGORITHMS
TOOLBOX

All Related Versions

Version 1, 2003-06-13, ArXiv
Published version: Journal of Computational and Applied Mathematics, 174 (2), 271.

This publication has 0 references indexed in Scilit: