Quicksort asymptotics
| dc.creator | Fill, James Allen | |
| dc.creator | Janson, Svante | |
| dc.date | 2001-05-29 | |
| dc.date.accessioned | 2026-07-07T04:41:55Z | |
| dc.date.available | 2026-07-07T04:41:55Z | |
| dc.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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/math/0105248 | |
| dc.identifier | http://arxiv.org/abs/math/0105248 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61559 | |
| dc.subject | Probability | |
| dc.subject | 68W40 (primary), 68P10, 60F05, 60E05 (secondary) | |
| dc.title | Quicksort asymptotics | |
| dc.type | text |