Time and space bounds for selection problems

David Dobkin, J. Ian Munro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The complexity of a number of selection problems is considered. An algorithm is given to determine the mode of a multiset in a number of comparisons differing from the lower bound by only a "lower order term." The problems of finding the kth largest element in a set in minimal and near minimal space are also discussed. A time space tradeoff is demonstrated for these problems.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 5th Colloquium
EditorsCorrado Bohm, Giorgio Ausiello
PublisherSpringer Verlag
Pages192-204
Number of pages13
ISBN (Print)9783540088608
DOIs
StatePublished - Jan 1 1978
Externally publishedYes
Event5th International Colloquium on Automata, Languages and Programming, ICALP 1978 - Udine, Italy
Duration: Jul 17 1978Jul 21 1978

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume62 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Colloquium on Automata, Languages and Programming, ICALP 1978
CountryItaly
CityUdine
Period7/17/787/21/78

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Time and space bounds for selection problems'. Together they form a unique fingerprint.

Cite this