Quicksort asymptotics
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
The number of comparisons X_n used by Quicksort to sort an array of n distinct numbers has mean mu_n of order n log n and standard deviation of order n. Using different methods, Regnier and Roesler each showed that the normalized variate Y_n := (X_n - mu_n) / 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 Y_n to that of Y, using various metrics. In particular, we establish the bound 2 n^{- 1 / 2} in the d_2-metric, and the rate O(n^{epsilon - (1 / 2)}) for Kolmogorov-Smirnov distance, for any positive epsilon.
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
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