On the densities of the limiting distributions for QuickSort and QuickQuant
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 scalenormalized number of key comparisons used by the algorithm QuickQuant(t) for 0 ≤ t ≤ 1, on the other hand, is somewhat limited and focuses on (nonlimiting and limiting) moments and the limiting distribution function Ft. In particular, except knowing that t = 0 and t = 1 corresponds to the wellknown 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 righttail 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 largedeviation results of QuickSort established by McDiarmid and Hayward (1996) and produce similar new (as far as we know) results for QuickQuant.
Collections
Related items
Showing items related by title, author, creator and subject.

QuickSelect Process and QuickVal Residual Convergence
Matterer, Jason (Johns Hopkins UniversityUSA, 20150922)We define a sequence of treeindexed processes closely related to the operation of the QuickSelect search algorithm (also known as Find) for all the various values of n (the number of input keys) and m (the rank of the ... 
(1) The Rail Road Quick Step; (2) The Carrollton Quick Step.
W. Broadbent (composer) (Geo. Willig, Jr., 1828)