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}$.
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
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • 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). 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〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

102