Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9509647 | Journal of Computational and Applied Mathematics | 2005 | 43 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
James Allen Fill, Philippe Flajolet, Nevin Kapur,