On the densities of the limiting distributions for QuickSort and QuickQuant
Embargo until
Date
2021-04-14
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
In this dissertation, we study in depth the limiting distribution of the costs of running the randomized sorting algorithm QuickSort and the randomized selection algorithm QuickQuant when the cost of sorting/selecting is measured by the number of key comparisons. It is well established in the literature that the limiting distribution F of the centered and scaled number of key comparisons required by QuickSort is infinitely differentiable and that the corresponding density function f enjoys superpolynomial decay in both tails. The first contribution of this dissertation is to establish upper and lower asymptotic bounds for the left and right tails of f that are nearly matching in each tail.
The literature study of the scale-normalized number of key comparisons used by the algorithm QuickQuant(t) for 0 ≤ t ≤ 1, on the other hand, is somewhat limited and focuses on (non-limiting and limiting) moments and the limiting distribution function Ft. In particular, except knowing that t = 0 and t = 1 corresponds to the well-known Dickman distribution, from the literature we do not know much about smoothness or decay properties of Ft for 0 < t < 1 except that 1 − Ft enjoys superexponential decay in the right tail. For t ∈ (0, 1), the second contribution of this dissertation is to prove that Ft has a Lipschitz continuous density function ft that is bounded above (by 10). We establish several fundamental properties of ft including positivity of ft(x) for every x > min{t, 1 − t} and infinite right differentiability at x = t. In particular, we prove that the survival function 1 − Ft(x) and the density function ft(x) both have the right-tail asymptotics exp[−x ln x − x ln ln x + O(x)].
The third contribution of this dissertation is to study large deviations of the number of key comparisons needed for both algorithms by using knowledge of the limiting distribution. In particular, we sharpen the large-deviation results of QuickSort established by McDiarmid and Hayward (1996) and produce similar new (as far as we know) results for QuickQuant.
Description
Keywords
QuickSort, QuickQuant, QuickSelect, QuickVal, densites, limiting distribution, asymptotic boundes, large deviations, moment generating functions.