Reference machines require non-linear time to maintain disjoint sets

Research output: Contribution to journalConference article

11 Scopus citations

Abstract

This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper shows that any such machine requires non-linear time in the worst case to compute unions of disjoint sets on-line. All set union algorithms known to the author are instances of the model and are thus subject to the derived bound. One of the known algorithms achieves the bound to within a constant factor.

Original languageEnglish (US)
Pages (from-to)18-29
Number of pages12
JournalProceedings of the Annual ACM Symposium on Theory of Computing
Volume02-04-May-1977
DOIs
StatePublished - May 4 1977
Externally publishedYes
Event9th Annual ACM Symposium on Theory of Computing, STOC 1977 - Boulder, United States
Duration: May 2 1977May 4 1977

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Reference machines require non-linear time to maintain disjoint sets'. Together they form a unique fingerprint.

  • Cite this