Optimal Time Minimal Space Selection Algorithms

David Dobkin, J. Ian Munro

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

Algorithms for findmg medians and solving arbitrary selection problems using a minimum number of data storage locations are investigated A linear-tmle algorithm is given in the first case, and it ~s shown that no such scheme exists for many other interesting selection problems, such as finding a quartile A right trade-off is demonstrated balancing extra space versus time.

Original languageEnglish (US)
Pages (from-to)454-461
Number of pages8
JournalJournal of the ACM (JACM)
Volume28
Issue number3
DOIs
StatePublished - Jul 1 1981

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • lower bound
  • median
  • minimum space
  • selection

Fingerprint Dive into the research topics of 'Optimal Time Minimal Space Selection Algorithms'. Together they form a unique fingerprint.

  • Cite this