The Expected Linearity of a Simple Equivalence Algorithm,

Abstract

The average time needed to form unions of disjoint equivalence classes, using an algorithm, is shown to be linear in the total number of elements. The analytic methods used to prove this result are of interest in themselves, as they are based on extensions of an approach to the study of random graphs.

Open PDF

Document Details

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

Entities

People

  • Arnold Schoenhage
  • Donald Knuth

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Equations
  • Identities
  • Information Processing
  • Integrals
  • Linearity
  • Military Research
  • Particles
  • Probability
  • Probability Distributions
  • Sequences
  • Statistical Mechanics
  • Terminals
  • Trees (Data Structures)
  • United States Government

Readers

  • Statistical inference.