Abstract
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 (n 1/2) comparisons can be made into a randomized algorithm that performs n+C+O(n 1/2 log3/2 n) comparisons with probability at least 1−1/n ρ, for any constant ρ>0.