Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430987 | Journal of Discrete Algorithms | 2007 | 17 Pages |
Abstract
The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
H.M. Okasha, U. Rösler,