Amortized Analysis of Algorithms for Set Union with Backtracking

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(nlog 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.