41 citations · 100 across the 6 of their papers we have counts for
6 papers
A repertoire for additive functionals of uniformly distributed m-ary search trees
James Allen Fill, Nevin Kapur
Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on -ary search trees on…
The space requirement of m-ary search trees: distributional asymptotics for m >= 27
James Allen Fill, Nevin Kapur
We study the space requirement of -ary search trees under the random permutation model when is fixed. Chauvin and Pouyanne have shown recently that , the space…
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…