The space requirement of m-ary search trees: distributional asymptotics for m >= 27

Abstract

We study the space requirement of $m$-ary search trees under the random permutation model when $m\ge 27$ is fixed. Chauvin and Pouyanne have shown recently that $X_n$, the space requirement of an $m$-ary search tree on $n$ keys, equals $\mu (n+1)+2\Re [\Lambda n^{{\lambda }_2}]+{\epsilon }_n{n}^{\Re {\lambda }_2}$, where $\mu$ and ${\lambda }_2$ are certain constants, $\Lambda$ is a complex-valued random variable, and ${\epsilon }_n\to 0$ a.s. and in $L^2$ as $n\to \infty$. Using the contraction method, we identify the distribution of $\Lambda$.

10 pages, 1 figure