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 g e q 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

m u (n + 1) + 2 R e [L a m b d a n^{l a m b d a_{2}}] + e p s i l o n_{n} n^{R e l a m b d a_{2}}

, where

m u

and

l a m b d a_{2}

are certain constants,

L a m b d a

is a complex-valued random variable, and

e p s i l o n_{n} o 0

a.s. and in

L^{2}

as

n o i n f t y

. Using the contraction method, we identify the distribution of

L a m b d a

.

This page was built for publication: The space requirement of m-ary search trees: distributional asymptotics for m >= 27