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

Alexandros V. Gerbessiotis; Constantinos J. Siniolakis

doi:10.1080/00207160512331331048

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

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 log^3/2 n) comparisons with probability at least 1 - 1/n ^ρ, for any constant ρ > 0.

Original language	English (US)
Pages (from-to)	509-519
Number of pages	11
Journal	International Journal of Computer Mathematics
Volume	82
Issue number	5
DOIs	https://doi.org/10.1080/00207160512331331048
State	Published - May 2005

All Science Journal Classification (ASJC) codes

Computer Science Applications
Computational Theory and Mathematics
Applied Mathematics

Keywords

Algorithms
Floyd-Rivest selection algorithm
Randomization
Selection

Access to Document

10.1080/00207160512331331048

Cite this

@article{75f4004a6d0a4113a6bf09e3868145fa,

title = "A probabilistic analysis of the Floyd-Rivest expected time selection algorithm",

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.",

keywords = "Algorithms, Floyd-Rivest selection algorithm, Randomization, Selection",

author = "Gerbessiotis, {Alexandros V.} and Siniolakis, {Constantinos J.}",

year = "2005",

month = may,

doi = "10.1080/00207160512331331048",

language = "English (US)",

volume = "82",

pages = "509--519",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

publisher = "Taylor and Francis Ltd.",

number = "5",

}

TY - JOUR

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

AU - Gerbessiotis, Alexandros V.

AU - Siniolakis, Constantinos J.

PY - 2005/5

Y1 - 2005/5

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

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

KW - Algorithms

KW - Floyd-Rivest selection algorithm

KW - Randomization

KW - Selection

UR - http://www.scopus.com/inward/record.url?scp=27844590008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=27844590008&partnerID=8YFLogxK

U2 - 10.1080/00207160512331331048

DO - 10.1080/00207160512331331048

M3 - Article

AN - SCOPUS:27844590008

SN - 0020-7160

VL - 82

SP - 509

EP - 519

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this