# Nicolas Pouyanne: What Happens When ?

## This is a joint work with Brigitte Chauvin.

It is known that the joint distribution of the number of nodes of each type of a -ary search tree is multivariate normal when ([LM94], [CH01], [Hwa02]).

When , we show the following strong () asymptotics of the random vector , where denotes the number of nodes containing keys after having introduced keys in the tree: there exists deterministic vectors , and and random variables and such that

and denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part.

## Bibliography

CH01
Hua-Huai Chern and Hsien-Kuei Hwang.
Phase changes in random -ary search trees and generalized quicksort.
Random Structures Algorithms, 19(3-4):316-358, 2001.
Analysis of algorithms (Krynica Morska, 2000).

Hwa02
Hsien-Kuei Hwang.
Second phase changes in random -ary search trees and generalized quicksort: convergence rates.
To appear in the Annals of Probability. Paper available at http://algo.stat.sinica.edu.tw/, 2002.

LM94
William Lew and Hosam M. Mahmoud.
The joint distribution of elastic buckets in multiway search trees.
SIAM J. Comput., 23(5):1050-1074, 1994.