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…