41 citations · 100 across the 6 of their papers we have counts for
4 papers · 1 filter
Singularity analysis, Hadamard products, and tree recurrences
James Allen Fill, Philippe Flajolet, Nevin Kapur
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 Had…
Limiting distributions for additive functionals on Catalan trees
James Allen Fill, Nevin Kapur
Additive tree functionals represent the cost of many divide-and-conquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the…
Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees
James Allen Fill, Nevin Kapur
We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of…
Additive functionals on random search trees
Nevin Kapur
Search trees are fundamental data structures in computer science. We study functionals on random search trees that satisfy recurrence relations of a simple additive form. Many impo…