41 citations · 100 across the 6 of their papers we have counts for
Showing 2003 · math.PRShow all
3 papers · 2 filters
math.PR2003★ 41 cited
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…
math.PR2003★ 18 cited
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…
math.PR2003★ 2 cited
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…