LIPIcs.AofA.2018.21.pdf
- Filesize: 346 kB
- 10 pages
Document
On the Tails of the Limiting QuickSort Density
Authors
-
Part of:
Volume:
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-18
Cite AsGet BibTex
James Allen Fill and Wei-Chun Hung. On the Tails of the Limiting QuickSort Density. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.21
https://doi.org/10.4230/LIPIcs.AofA.2018.21
Abstract
We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.
Subject Classification
ACM Subject Classification
- Theory of computation → Sorting and searching
- Mathematics of computing → Distribution functions
Keywords
- Quicksort
- density tails
- asymptotic bounds
- Landau-Kolmogorov inequality
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- James Allen Fill and Svante Janson. A characterization of the set of fixed points of the Quicksort transformation. Electron. Comm. Probab., 5:77-84, 2000. URL: http://dx.doi.org/10.1214/ECP.v5-1021.
-
James Allen Fill and Svante Janson. Smoothness and decay properties of the limiting quicksort density function. Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, pages 53-64, 2000.
-
Svante Janson. On the tails of the limiting quicksort distribution. Electronic Communications in Probability, 20, 2015.
-
Charles Knessl and Wojciech Szpankowski. Quicksort algorithm again revisited. Discrete Mathematics and Theoretical Computer Science, 3(2), 1999.
-
A. P. Matorin. On inequalities between the maxima of the absolute values of a function and its derivatives on a half-line. Ukrain. Mat. Ž., 7:262-266, 1955.
- D. S. Mitrinović, J. E. Pečarić, and A. M. Fink. Inequalities involving functions and their integrals and derivatives, volume 53 of Mathematics and its Applications (East European Series). Kluwer Academic Publishers Group, Dordrecht, 1991. URL: http://dx.doi.org/10.1007/978-94-011-3562-7.
-
Mireille Régnier. A limiting distribution for quicksort. RAIRO-Theoretical Informatics and Applications, 23(3):335-343, 1989.
-
Uwe Rösler. A limit theorem for "quicksort". RAIRO-Theoretical Informatics and Applications, 25(1):85-100, 1991.
-
Sergei Borisovich Stechkin. Inequalities between the upper bounds of the derivatives of an arbitrary function on the half-line. Mathematical notes of the Academy of Sciences of the USSR, 1(6):442-447, 1967.