A class of algorithms which require nonlinear time to maintain disjoint sets

Research output: Contribution to journalArticle

161 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 defines a class of algorithms which compute unions of disjoint sets on-line, and proves that any such algorithm requires nonlinear time in the worst case. 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)110-127
Number of pages18
JournalJournal of Computer and System Sciences
Volume18
Issue number2
DOIs
StatePublished - Apr 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A class of algorithms which require nonlinear time to maintain disjoint sets'. Together they form a unique fingerprint.

  • Cite this