Name
Abstract | ||
|---|---|---|
We characterize all limit laws of the quicksort-type random variables defined recursively by ${\cal L}(X_n)= {\cal L}(X_{I_n}+X^*_{n-1-I_n}+T_n)$ when the "toll function" Tn varies and satisfies general conditions, where (Xn), (Xn*), (In, Tn) are independent, In is uniformly distributed over {0, . . .,n-1}, and ${\cal L}(X_n)={\cal L}(X_n^\ast)$. When the "toll function" Tn (cost needed to partition the original problem into smaller subproblems) is small (roughly $\limsup_{n\rightarrow\infty}\log E(T_n)/\log n\le 1/2$), Xn is asymptotically normally distributed; nonnormal limit laws emerge when Tn becomes larger. We give many new examples ranging from the number of exchanges in quicksort to sorting on a broadcast communication model, from an in-situ permutation algorithm to tree traversal algorithms, etc. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1137/S009753970138390X | SIAM J. Comput. |
Keywords | Field | DocType |
limit laws,method of moments,toll function,binary search trees,varying toll functions,cal l,nonnormal limit law,contraction method abbreviated title: limit laws of quicksort recurrence,log n,quicksort recurrence,general condition,limit distribution,broadcast communication model,in-situ permutation algorithm,log e,analysis of algorithms,limit law,quicksort,new example,binary search tree,phase change,random variable | Limit of a function,Discrete mathematics,Binary logarithm,Combinatorics,Random variable,Analysis of algorithms,Permutation,Quicksort,Partition (number theory),Binary search tree,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 6 | 0097-5397 |
Citations | PageRank | References |
30 | 1.62 | 40 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsien-Kuei Hwang | 1 | 365 | 38.02 |
| Ralph Neininger | 2 | 138 | 15.56 |