41 citations · 98 across the 5 of their papers we have counts for
5 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…