# Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)

Abstract : Using a recursive approach, we obtain a simple exact expression for the $L^2$-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by $\texttt{QuickSort}$. A previous study by Fill and Janson (2002) using a similar approach found that the $d_2$-distance is of order between $n^{-1} \log{n}$ and $n^{-1/2}$, and another by Neininger and Ruschendorf (2002) found that the Zolotarev $\zeta _3$-distance is of exact order $n^{-1} \log{n}$. Our expression reveals that the $L^2$-distance is asymptotically equivalent to $(2 n^{-1} \ln{n})^{1/2}$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [6 references]

https://hal.inria.fr/hal-01197222
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:54:40 PM
Last modification on : Monday, January 27, 2020 - 11:06:02 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:32:36 AM

### File

dmAQ0125.pdf
Publisher files allowed on an open archive

### Citation

Patrick Bindjeme, James Allen Fill. Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract). 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.339-348, ⟨10.46298/dmtcs.3003⟩. ⟨hal-01197222⟩

Record views