Skip to Main content Skip to Navigation
Conference papers

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}$.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01197222
Contributor : Coordination Episciences Iam <>
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

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01197222, version 1

Collections

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. ⟨hal-01197222⟩

Share

Metrics

Record views

196

Files downloads

641