We present a probabilistic analysis of the Floyd-Rivest expected time selection algorithm. In particular, we show that a refinement of the bootstrapped version of the Floyd-Rivest algorithm that determines the Cth order statistic by performing an expected n + C + O(n1/2) comparisons can be made into a randomized algorithm that performs n + C + O(n1/2 log3/2 n) comparisons with probability at least 1 - 1/n ρ, for any constant ρ > 0.
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Computational Theory and Mathematics
- Applied Mathematics
- Floyd-Rivest selection algorithm