Perfect simulation from the Quicksort limit distribution

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The 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.
7 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

Keywords

Probability, Data Structures and Algorithms, 65C10 (primary), 65C05, 68U20, 11K45 (secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/59270

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0005237
 http://arxiv.org/abs/math/0005237

Collections

arXiv