Smoothness and decay properties of the limiting Quicksort density function

Preprint

23 May 2000

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.math/0005235

Abstract

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 plus and minus infinity. In particular, each f^{(k)} is bounded. Our method is sufficiently computational to prove, for example, that f is bounded by 16.

Keywords

INFINITELY DIFFERENTIABLE
ENJOYS SUPERPOLYNOMIAL
DIFFERENTIABLE DENSITY
LIMITING QUICKSORT
QUICKSORT DENSITY
DECAY PROPERTIES
FOURIER ANALYSIS
USING FOURIER

All Related Versions

Version 1, 2000-05-23, ArXiv

This publication has 0 references indexed in Scilit: