Second phase changes in random m-ary search trees and generalized quicksort: Convergence rates
-
Hsien-Kuei Hwang [1]
-
[1] Academia Sinica
Academia Sinica
Taiwán
-
- Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 31, Nº. 2, 2003, págs. 609-629
- Idioma: inglés
- DOI: 10.1214/aop/1048516530
- Texto completo no disponible (Saber más ...)
-
Resumen
We study the convergence rate to normal limit law for the space requirement of random m-ary search trees. While it is known that the random variable is asymptotically normally distributed for 3≤m≤26 and that the limit law does not exist for m>26, we show that the convergence rate is O(n−1/2) for 3≤m≤19 and is O(n−3(3/2−α)), where 4/3<α<3/2 is a parameter depending on m for 20≤m≤26. Our approach is based on a refinement to the method of moments and applicable to other recursive random variables; we briefly mention the applications to quicksort proper and the generalized quicksort of Hennequin, where more phase changes are given. These results provide natural, concrete examples for which the Berry--Esseen bounds are not necessarily proportional to the reciprocal of the standard deviation. Local limit theorems are also derived.
