An optimally efficient selection algorithm

Research output: Contribution to journalArticlepeer-review

Abstract

We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log*/log log n) time.

Original languageEnglish (US)
Pages (from-to)295-299
Number of pages5
JournalInformation Processing Letters
Volume26
Issue number6
DOIs
StatePublished - Jan 25 1988

Keywords

  • Selection
  • optimal algorithm
  • parallel algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'An optimally efficient selection algorithm'. Together they form a unique fingerprint.

Cite this