2001/05/29 by James Allen Fill, Svante Janson, Fill, James Allen +1
Mathematics · #60E05 (secondary) #60F05 #68P10 #68W40 (primary) #Analytic Number Theory Research #FOS: Mathematics #Mathematical Approximation and Integration #Mathematical Dynamics and Fractals #Probability (math.PR) #math.PR #msc:60E05 #msc:60F05 #msc:68P10 #msc:68W40
paper · pdf · doi:10.48550/arxiv.math/0105248
23 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/ . To be submitted for publication in May, 2001
arxiv created 2001/05/29 · openalex publication_date 2001/05/29 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean mun of order n log n and standard deviation of order n. Using different methods, Regnier and Roesler each showed that the normalized variate Yn := (Xn - mun) / n converges in distribution, say to Y; the distribution of Y can be characterized as the unique fixed point with zero mean of a certain distributional transformation. We provide the first rates of convergence for the distribution of Yn to that of Y, using various metrics. In particular, we establish the bound 2 n- 1 / 2 in the d2-metric, and the rate O(nepsilon - (1 / 2)) for Kolmogorov-Smirnov distance, for any positive epsilon.