Smoothness and decay properties of the limiting Quicksort density function

Simple item page
dc.creatorFill, James Allen
dc.creatorJanson, Svante
dc.date2000-05-23
dc.date.accessioned2026-07-07T04:35:29Z
dc.date.available2026-07-07T04:35:29Z
dc.descriptionUsing 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.
dc.description11 pages. Refereed article, to apppear in a book edited by D. Gardy and A. Mokkadem and published in 2000 by Birkhauser
dc.identifierhttps://arxiv.org/abs/math/0005235
dc.identifierhttp://arxiv.org/abs/math/0005235
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/59268
dc.subjectProbability
dc.subjectData Structures and Algorithms
dc.subject68W40 (primary), 68P10, 60E05, 60E10 (secondary)
dc.titleSmoothness and decay properties of the limiting Quicksort density function
dc.typetext

Files

Collections

arXiv