A probabilistic analysis of the Floyd-Rivest expected time selection algorithm

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

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(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.

Original languageEnglish (US)
Pages (from-to)509-519
Number of pages11
JournalInternational Journal of Computer Mathematics
Volume82
Issue number5
DOIs
StatePublished - May 1 2005

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Algorithms
  • Floyd-Rivest selection algorithm
  • Randomization
  • Selection

Fingerprint Dive into the research topics of 'A probabilistic analysis of the Floyd-Rivest expected time selection algorithm'. Together they form a unique fingerprint.

Cite this