Patrick Bindjeme ; james Allen fill - The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract)

dmtcs:3004 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.3004
The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract)

Authors: Patrick Bindjeme 1; james Allen fill

  • 1 Department of Applied Mathematics and Statistics [Baltimore]

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.

https://doi.org/10.46298/dmtcs.3004
Source: HAL:hal-01197223v1
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: Chebyshev's other inequality,key comparisons,QuickSort,limit distribution,$L^p$-convergence,symbol comparisons,probabilistic source,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1202.2601
Source : ScholeXplorer IsRelatedTo DOI 10.1214/12-aap866
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1202.2601
  • 10.1214/12-aap866
  • 10.48550/arxiv.1202.2601
  • 1202.2601
Distributional convergence for the number of symbol comparisons used by QuickSort

Share and export

Consultation statistics

This page has been seen 156 times.
This article's PDF has been downloaded 161 times.