Refined Quicksort asymptotics

2012/07/19 by Ralph Neininger, Neininger, Ralph
Computer Science · Mathematics · #60F05 #60F15 #68P10 #68Q25 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DS #math.PR #msc:60F05 #msc:60F15 #msc:68P10 #msc:68Q25

paper · pdf · doi:10.48550/arxiv.1207.4556

revised version; title slightly changed; accepted for publication in Random Structures and Algorithms

arxiv created 2013/01/24 · arxiv updated 2013/01/25

Abstract

The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of n data, permuted uniformly at random, the appropriately normalized complexity Y_n is known to converge almost surely to a non-degenerate random limit Y. This assumes a natural embedding of all Y_n on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown: √((n)/(2log n))(Y_n-Y) \stackreld\longrightarrow \cal N (n→∞), where \cal N denotes a standard normal random variable.

Related

• Approximating the limiting Quicksort distribution
• Quicksort asymptotics
• Perfect simulation from the Quicksort limit distribution
• Convergence of the QuickVal Residual
• A local limit theorem for Quicksort key comparisons via multi-round smoothing