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 \geq 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 $μ(n+1) + 2\Re{[Λn^{λ_2}]} + ε_n n^{\Re{λ_2}}$, where $μ$ and $λ_2$ are certain constants, $Λ$ is a complex-valued random variable, and $ε_n \to 0$ a.s. and in $L^2$ as $n \to \infty$. Using the contraction method, we identify the distribution of $Λ$.

10 pages, 1 figure