Refined quicksort asymptotics. Issue 2 (12th April 2013) - Neininger, Ralph
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 Yn is known to converge almost surely to a non‐degenerate random limit Y. This assumes a natural embedding of all Yn 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: <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734fzt1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n2logn(Yn−Y)→dN (n→∞), </alternatives> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734g01b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />N</alternatives> denotes a standard normal random variable. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 346–361, 2015