|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Smoothness and decay properties of the limiting Quicksort density function | | James Allen Fill
; Svante Janson
; | | Date: |
23 May 2000 | | Subject: | Probability; Data Structures and Algorithms MSC-class: 68W40 (primary), 68P10, 60E05, 60E10 (secondary) | math.PR cs.DS | | Affiliation: | Johns Hopkins Univ.), Svante Janson (Uppsala Univ. | | 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. | | Source: | arXiv, math.PR/0005235 | | 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