DOAJ Open Access 2012

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

Patrick Bindjeme james Allen fill

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (2)

Patrick Bindjeme

james Allen fill

Format Sitasi

APA MLA BibTeX

Bindjeme, P., fill, j.A. (2012). The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract). https://doi.org/10.46298/dmtcs.3004

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3004

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3004
Akses: Open Access ✓