Reference Machines Require Non-Linear Time to Maintain Disjoint Sets.

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 me 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. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1977
Accession Number
ADA041292

Entities

People

  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Automata
  • Bits
  • Compression
  • Computational Complexity
  • Computer Science
  • Computers
  • Construction
  • Hash Tables
  • Instructions
  • Language
  • Machines
  • Numbers
  • Real Numbers
  • Sequences
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Computational Modeling and Simulation
  • Computer Science.