Premium
Phase changes in random m ‐ary search trees and generalized quicksort
Author(s) -
Chern HuaHuai,
Hwang HsienKuei
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10005
Subject(s) - quicksort , mathematics , limiting , combinatorics , partition (number theory) , discrete mathematics , asymptotic distribution , distribution (mathematics) , algorithm , statistics , mathematical analysis , sorting , mechanical engineering , sorting algorithm , estimator , engineering
We propose a uniform approach to describe the phase change of the limiting distribution of space measures in random m ‐ary search trees: the space requirement, when properly normalized, is asymptotically normally distributed for m ≤26 and does not have a fixed limiting distribution for m >26. Our tools are based on the method of moments and asymptotic solutions of differential equations, and are applicable to secondary cost measures of quicksort with median‐of‐(2 t +1) for which the same phase change occurs at t =58. Both problems are essentially special cases of the generalized quicksort of Hennequin in which a sample of m ( t +1)−1 elements are used to select m −1 equi‐spaced ranks that are used in turn to partition the input into m subfiles. A complete description of the numbers at which the phase change occurs is given. For example, when m is fixed and t varies, the phase change occurs at ( m , t )={(2, 58), (3, 19), (4, 10), (5, 6), (6, 4), …}. We also indicate some applications of our approach to other problems including bucket recursive trees. A general framework on “asymptotic transfers” of the underlying recurrence is also given. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 316–358, 2001