Smoothness and decay properties of the limiting Quicksort density function

Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and infinitely differentiable density f, and that each derivative f (k) enjoys superpolynomial decay at ±∞. In particular, each f (k) is bounded. Our method is sufficiently computational to prove, for example, that f is bounded by 16.

• Publication year

  2000

• Venue

  arXiv.org

• Publication date

  2000-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-0348-8405-1_5arXiv math/0005235
• 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 Algorithm Again Revisited

  1999cited by this paper
• The Art of Computer Programming: Volume 3: Sorting and Searching

  1998cited by this paper
• How Many Comparisons Does Quicksort Use?

  1995cited by this paper
• Some properties of a limiting distribution in Quicksort

  1995cited by this paper
• Ten lectures on the interface between analytic number theory and harmonic analysis

  1994cited by this paper
• A limit theorem for "Quicksort"

  1991influential reference
• Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche

  1991cited by this paper
• Combinatorial Analysis of Quicksort Algorithm

  1989cited by this paper
• A Limiting Distribution for Quicksort

  1989cited by this paper
• The art of computer programming

  1983cited by this paper
• An introduction to probability theory and its applications. Vol. II

  1968cited by this paper
• Théorie des distributions

  1966influential reference
• An Introduction to Probability Theory and Its Applications

  1959cited by this paper
• Zahlentheoretische Abschätzungen

  year unknowncited by this paper

• Probabilistic analysis of optimal multi-pivot QuickSort

  2025cites this paper
• Stochastic fixed-point equations

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

  2019cites this paper
• Arbres pour l'algorithmique

  2018cites this paper
• Arbres binaires de recherche

  2018cites this paper
• A Note on the Approximation of Perpetuities Margarete Knape

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

  2018cites 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
• Asymptotiques de fonctionnelles d'arbres aléatoires et de graphes denses aléatoires

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

  2017cites this paper
• Probabilistic Analysis of the Dual-Pivot Quicksort "Count"

  2017influential citation
• A local limit theorem for Quicksort key comparisons via multi-round smoothing

  2017influential citation
• On densities for solutions to stochastic fixed point equations

  2016influential citation
• On the exponential decay of the characteristic function of the quicksort distribution

  2016influential citation
• On the tails of the limiting Quicksort distribution

  2015cites this paper
• Limit laws for functions of fringe trees for binary search trees and random recursive trees

  2015influential citation
• Limit Laws for Functions of Fringe trees for Binary Search Trees and Recursive Trees

  2014influential citation
• Sample Based Curve Fitting Computation on the Performance of Quicksort in Personal Computer

  2014cites this paper
• Average Case and Distributional Analysis of Dual-Pivot Quicksort

  2013cites this paper
• Running time of the Treapsort algorithm

  2013cites this paper
• Average Case and Distributional Analysis of Java 7's Dual Pivot Quicksort

  2013cites this paper
• Asymptotic Analysis of Hoppe Trees

  2012cites this paper
• Distributional convergence for the number of symbol comparisons used by QuickSort

  2012influential citation
• Partial quicksort and weighted branching processes

  2011cites this paper
• ON THE SILHOUETTE OF BINARY SEARCH TREES BY RUDOLF GRÜBEL Leibniz Universität Hannover

  2009cites this paper
• On the silhouette of binary search trees

  2009cites this paper
• On the silhouette of binary search trees

  2009cites this paper
• Approximating Perpetuities

  2007cites this paper
• A Note on the Approximation of Perpetuities

  2007cites this paper
• Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform

  2006cites this paper
• Probabilistic analysis of algorithms , stochastic fixed-point equations and ideal metrics

  2006cites this paper
• Applications of Stein's method in the analysis of random binary search trees

  2005cites this paper
• Stochastische Analyse von Algorithmen, Fixpunktgleichungen und ideale Metriken

  2004cites this paper
• PROFILE AND HEIGHT OF RANDOM BINARY SEARCH TREES

  2004cites this paper
• The number of bit comparisons used by Quicksort: an average-case analysis

  2004cites this paper
• Stochastic analysis of tree–like data structures

  2004cites this paper
• Additive functionals on random search trees

  2003cites this paper
• On fixed points of Poisson shot noise transforms

  2002cites this paper
• Rates of convergence for Quicksort

  2002cites this paper
• On binary search tree recursions with monomials as toll functions

  2002influential citation
• Density approximation and exact simulation of random variables that are solutions of fixed-point equations

  2002influential citation
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions

  2002cites this paper
• ARE SOLUTIONS OF FIXED-POINT EQUATIONS

  2002cites this paper
• Approximating the limiting Quicksort distribution

  2001influential citation
• Approximating the Limiting Qui ksort

  2001cites this paper
• Quicksort asymptotics

  2001influential citation
• Exact Simulation of Random Variables that are Solutions of Fixed-Point Equations

  2001influential citation
• Approximations ofthe Limiting Quicksort Distribution ( SECOND DRAFT )

  2000cites this paper
• A characterization of the set of fixed points of the Quicksort transformation

  2000cites this paper
• Perfect simulation from the Quicksort limit distribution

  2000influential citation