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

James Allen Fill, Nevin Kapur

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…