Perfect simulation from the Quicksort limit distribution

Simple item page
dc.creatorDevroye, Luc
dc.creatorFill, James Allen
dc.creatorNeininger, Ralph
dc.date2000-05-23
dc.date2000-05-23
dc.date.accessioned2026-07-07T04:35:29Z
dc.date.available2026-07-07T04:35:29Z
dc.descriptionThe weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation. We give an algorithm for perfect random variate generation from this distribution.
dc.description7 pages. See also http://www.mts.jhu.edu/~fill/, http://www-cgrl.cs.mcgill.ca/~luc/, and http://www.stochastik.uni-freiburg.de/homepages/neininger/ . Submitted for publication in May, 2000
dc.identifierhttps://arxiv.org/abs/math/0005237
dc.identifierhttp://arxiv.org/abs/math/0005237
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/59270
dc.subjectProbability
dc.subjectData Structures and Algorithms
dc.subject65C10 (primary), 65C05, 68U20, 11K45 (secondary)
dc.titlePerfect simulation from the Quicksort limit distribution
dc.typetext

Files

Collections

arXiv