On the tails of the limiting Quicksort distribution

We give asymptotics for the left and right tails of the limiting Quicksort distribution. The results agree with, but are less precise than, earlier non-rigorous results by Knessl and Spankowski.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-04-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/ECP.V20-4525arXiv 1508.07230
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quicksort asymptotics

  2001cited by this paper
• Approximating the limiting Quicksort distribution

  2001influential reference
• A characterization of the set of fixed points of the Quicksort transformation

  2000cited by this paper
• Smoothness and decay properties of the limiting Quicksort density function

  2000cited by this paper
• Quicksort Algorithm Again Revisited

  1999influential reference
• Large Deviations for Quicksort

  1996influential reference
• Some properties of a limiting distribution in Quicksort

  1995influential reference
• A limit theorem for "Quicksort"

  1991influential reference
• A Limiting Distribution for Quicksort

  1989influential reference
• The art of computer programming

  1983cited by this paper
• The art of computer programming: sorting and searching (volume 3)

  1973cited by this paper

• Density functions for QuickQuant and QuickVal

  2021cites this paper
• Upper Tail Analysis of Bucket Sort and Random Tries

  2020cites this paper
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)

  2019cites this paper
• Logarithmic integrals, zeta values, and tiered binomial coefficients

  2019cites this paper
• 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018, Uppsala, Sweden, June 25-29, 2018

  2018cites this paper
• On the Tails of the Limiting QuickSort Density

  2018influential citation
• Exact and approximate limit behaviour of the Yule tree’s cophenetic index

  2017cites this paper
• Convergence of the population dynamics algorithm in the Wasserstein metric

  2017cites this paper
• Generalized PageRank on directed configuration networks

  2017cites this paper
• On densities for solutions to stochastic fixed point equations

  2016cites this paper
• Thin tails of fixed points of the nonhomogeneous smoothing transform

  2015influential citation