Amortized Analysis of Algorithms for Set Union with Backtracking
Authors:
- Jeffery WestbrookJWJeffery Westbrook
- Robert E. TarjanRTRobert E. Tarjan
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (1) , 1-11
Abstract
Mannila and Ukkonen [Lecture Notes in Computer Science 225, Springer-Verlag, New York, 1986, pp. 236–243] 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 \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 $\Omega ({{\log n} / {\log \log n}})$ time per operation, thus showing that our upper bound on amortized time is tight.
Keywords
This publication has 10 references indexed in Scilit:
- A lower bound for the complexity of the Union-Split-Find problem1987
- On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union ProblemSIAM Journal on Computing, 1986
- The set union problem with backtracking1986
- On the complexity of unification sequences1986
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- Amortized Computational ComplexitySIAM Journal on Algebraic Discrete Methods, 1985
- Worst-case Analysis of Set Union AlgorithmsJournal of the ACM, 1984
- Storage Modification MachinesSIAM Journal on Computing, 1980
- A class of algorithms which require nonlinear time to maintain disjoint setsJournal of Computer and System Sciences, 1979
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975