Name
Abstract | ||
|---|---|---|
We propose a uniform approach to describing 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 xed limit distribution for m > 26. The tools are based on the method of moments and asymptotic solutions of dierential equations, and are applicable to secondary cost measures of quicksort with median-of-(2t + 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 subles. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1002/rsa.10005 | Random Struct. Algorithms |
Keywords | Field | DocType |
random m-ary search tree,generalized quicksort,phase change | Differential equation,Discrete mathematics,Combinatorics,Normalization (statistics),struct,Quicksort,Partition (number theory),Recursion,Mathematics,Asymptotic distribution,Method of moments (statistics) | Journal |
Volume | Issue | ISSN |
19 | 3-4 | 1042-9832 |
Citations | PageRank | References |
21 | 1.58 | 22 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hua-Huai Chern | 1 | 78 | 7.25 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |