License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.21
URN: urn:nbn:de:0030-drops-89144
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8914/
Fill, James Allen ;
Hung, Wei-Chun
On the Tails of the Limiting QuickSort Density
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.
BibTeX - Entry
@InProceedings{fill_et_al:LIPIcs:2018:8914,
author = {James Allen Fill and Wei-Chun Hung},
title = {{On the Tails of the Limiting QuickSort Density}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {21:1--21:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8914},
URN = {urn:nbn:de:0030-drops-89144},
doi = {10.4230/LIPIcs.AofA.2018.21},
annote = {Keywords: Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality}
}
|
Keywords: |
|
Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality |
|
Collection: |
|
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.06.2018 |
