zbMATH — the first resource for mathematics

Refined Quicksort asymptotics. (English) Zbl 1327.68086
Summary: The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of \(n\) data, permuted uniformly at random, the appropriately normalized complexity \(Y_n\) is known to converge almost surely to a non-degenerate random limit \(Y\). This assumes a natural embedding of all \(Y_n\) on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown:
\[ \sqrt{\frac{n}{2\log n}}(Y_n-Y)\overset {d} \longrightarrow\mathcal{N} \quad {(n}\infty) \]
where \(\mathcal{N}\) denotes a standard normal random variable.

68P10 Searching and sorting
60F05 Central limit and other weak theorems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] Bindjeme, Exact L2-distance from the limit for quicksort key comparisons (Extended abstract), in: DMTCS proc., 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’12) pp 339– (2012) · Zbl 1296.68039
[2] Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann Math Stat 23 pp 493– (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[3] Chow, Independence, interchangeability, martingales, Springer Texts in Statistics, 3. ed. (1997)
[4] Drmota, A functional limit theorem for the profile of search trees, Ann Appl Probab 18 pp 288– (2008) · Zbl 1143.68019 · doi:10.1214/07-AAP457
[5] Evans, Trickle-down processes and their boundaries, Electron J Probab 17 pp 1– (2012) · Zbl 1246.60100 · doi:10.1214/EJP.v17-1698
[6] Fill, Quicksort asymptotics, J Algor 44 pp 4– (2002) · Zbl 1011.68028 · doi:10.1016/S0196-6774(02)00216-X
[7] R. Grübel Search trees: metric aspects and strong limit theorems (2012) http://arxiv.org/abs/1209.2546
[8] Hoare, Quicksort, Comput J 5 pp 10– (1962) · doi:10.1093/comjnl/5.1.10
[9] Knuth, Addison-Wesley Series in Computer Science and Information Processing, 2. ed. (1998)
[10] Mahmoud, Evolution of random search trees (1992) · Zbl 0762.68033
[11] Mahmoud, Sorting. A distribution theory (2000) · doi:10.1002/9781118032886
[12] McDiarmid, Concentration, Probabilistic methods for algorithmic discrete mathematics, Algorithms Combin 16 pp 195– (1998) · doi:10.1007/978-3-662-12788-9_6
[13] Neininger, Rates of convergence for quicksort, J Algor 44 pp 52– (2002) · Zbl 1010.68049 · doi:10.1016/S0196-6774(02)00206-7
[14] Neininger, A general limit theorem for recursive algorithms and combinatorial structures, Ann Appl Probab 14 pp 378– (2004) · Zbl 1041.60024 · doi:10.1214/aoap/1075828056
[15] Régnier, A limiting distribution for quicksort, RAIRO Inform Théor Appl 23 pp 335– (1989)
[16] Rösler, A limit theorem for ”Quicksort”, RAIRO Inform Théor Appl 25 pp 85– (1991)
[17] Zolotarev, Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces, Theor Probab Appl 21 pp 721– (1976) · Zbl 0378.60003 · doi:10.1137/1121086
[18] Zolotarev, Ideal metrics in the problem of approximating distributions of sums of independent random variables, Theory Probab Appl 22 pp 433– (1977) · Zbl 0385.60025 · doi:10.1137/1122056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.