# The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract)

Abstract : In a continuous-time setting, Fill (2012) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by $\texttt{QuickSort}$, when centered by subtracting the mean and scaled by dividing by time, has a limiting distribution, but proved little about that limiting random variable $Y$—not even that it is nondegenerate. We establish the nondegeneracy of $Y$. The proof is perhaps surprisingly difficult.
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.349-360, 2012, DMTCS Proceedings
Domaine :

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

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

### Fichier

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

### Identifiants

• HAL Id : hal-01197223, version 1

### Citation

Patrick Bindjeme, James Allen Fill. The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (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.349-360, 2012, DMTCS Proceedings. 〈hal-01197223〉

### Métriques

Consultations de la notice

## 151

Téléchargements de fichiers