|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A characterization of the set of fixed points of the Quicksort transformation | | James Allen Fill
; Svante Janson
; | | Date: |
23 May 2000 | | Subject: | Probability; Data Structures and Algorithms MSC-class: 68W40 (primary), 60E05, 60E10, 68P10 (secondary) | math.PR cs.DS | | Affiliation: | Johns Hopkins Univ.), Svante Janson (Uppsala Univ. | | Abstract: | The limiting distribution mu of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T -- unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of T if and only if it is the convolution of mu with a Cauchy distribution of arbitrary center and scale. In particular, therefore, mu is the unique fixed point of T having zero mean. | | Source: | arXiv, math.PR/0005236 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER