SIAM Journal on Computing · 2002 · 89 citations · 47 references
Natural SciencesMathematicsInformation TheoryProbability TheoryStochastic ProcessesLimit TheoremsMarkov ProcessesBroadcastHeavy-tailed Limit TheoremsLimit LawsLimit Theorems For Dependent Random VariablesQuicksortRecurrence
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.
47
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
PE, P. Billingsley · Journal of the American Statistical Association · 1996 · 6.7K citations
Some Asymptotic Theory for the Bootstrap
Peter J. Bickel, David A. Freedman · The Annals of Statistics · 1981 · 1.7K citations · Full text