A repertoire for additive functionals of uniformly distributed m-ary search trees

Abstract

Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on $m$-ary search trees on $n$ keys with toll sequence (i) $n^{\alpha }$ with $\alpha \ge 0$ ($\alpha =0$ and $\alpha =1$ correspond roughly to the space requirement and total path length, respectively); (ii) $\ln \left(\genfrac{}{}{0ex}{}{n}{m-1}\right)$, which corresponds to the so-called shape functional; and (iii) $1_{n=m-1}$, which corresponds to the number of leaves.

26 pages; v2 expands on the introduction by comparing the results with other probability models