zbMATH — the first resource for mathematics

A note on the Quicksort asymptotics. (English) Zbl 1332.68039
Summary: In a recent paper, P. Bindjeme and J. A. Fill [in: Proceeding of the 23rd international meeting on probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms, AofA’12. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). 339–348 (2012; Zbl 1296.68039)] obtained a surprisingly easy exact formula for the \(L_{2}\)-distance of the (normalized) number of comparisons of Quicksort under the uniform model to its limit. Shortly afterwards, R. Neininger proved [Random Struct. Algorithms 46, No. 2, 346–361 (2015; Zbl 1327.68086)] a central limit theorem for the error. As a consequence, he obtained the asymptotics of the \(L_{3}\)-distance. In this short note, we use the moment transfer approach to re-prove Neininger’s result. As a consequence, we obtain the asymptotics of the \(L_{p}\)-distance for all \(1\leq p<\infty\).

68P10 Searching and sorting
60G42 Martingales with discrete parameter
Full Text: DOI
[1] Bindjeme, 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms pp 339– (2012)
[2] Chern, An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms, J Algor 44 pp 177– (2002) · Zbl 1030.68114 · doi:10.1016/S0196-6774(02)00208-0
[3] Fill, Quicksort asymptotics, J Algor 44 pp 4– (2002) · Zbl 1011.68028 · doi:10.1016/S0196-6774(02)00216-X
[4] Fill, Transfer theorems and asymptotic distributional results for m-ary search trees, Random Struct Algor 26 pp 359– (2005) · Zbl 1101.68018 · doi:10.1002/rsa.20039
[5] Flajolet, An introduction to the analysis of algorithms (1996)
[6] Hoare, Quicksort, Comput J 5 pp 10– (1962) · doi:10.1093/comjnl/5.1.10
[7] Hwang, Phase change of limit laws in the Quicksort recurrences under varying toll functions, SIAM J Comput 31 pp 1687– (2002) · Zbl 1008.68166 · doi:10.1137/S009753970138390X
[8] Neininger, Refined Quicksort asymptotics, Random Struct Algor
[9] Neininger, Rates of convergence of Quicksort, J Algor 44 pp 52– (2002) · Zbl 1010.68049 · doi:10.1016/S0196-6774(02)00206-7
[10] Régnier, A limiting distribution for ”Quicksort”, RAIRO Inform Théor Appl 23 pp 335– (1989) · Zbl 0677.68072
[11] Rösler, A limit theorem for ”Quicksort”, RAIRO Inform Théor Appl 25 pp 85– (1991)
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.