# 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 :
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.339-348, 2012, DMTCS Proceedings
Domaine :

Littérature citée [6 références]

https://hal.inria.fr/hal-01197222
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:40
Dernière modification le : mardi 7 mars 2017 - 15:18:57
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:32:36

### Fichier

dmAQ0125.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01197222, version 1

### Citation

Patrick Bindjeme, James Allen Fill. Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract). Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.339-348, 2012, DMTCS Proceedings. 〈hal-01197222〉

### Métriques

Consultations de la notice

## 172

Téléchargements de fichiers