Amortized analysis of algorithms for set union with backtracking

Jeffery Westbrook, Robert Endre Tarjan

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

H. Mannila and E. Ukkonen (1986) have studied a variant of the classical disjoint set union (equivalence) problem in which an extra operation, called de-union, can undo the most recently performed union operation not yet undone. They proposed a way to modify standard set union algorithms to handle de-union operations. In this paper several algorithms are analyzed based on their approach. The most efficient such algorithms have an amortized running time of O(log n/log n) per operation, where n is the total number of elements in all the sets. These algorithms use O(n log n) space, but the space usage can be reduced to O(n) by a simple change. The authors prove that any separable pointer-based algorithm for the problem requires Ω(log n/log log n) time per operation, thus showing that our upper bound on amortized time is tight.

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalSIAM Journal on Computing
Volume18
Issue number1
DOIs
StatePublished - Jan 1 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Amortized analysis of algorithms for set union with backtracking'. Together they form a unique fingerprint.

  • Cite this