JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Efficiency of a Good but Not Linear Set Union Algorithm

Author
Tarjan, Robert Endre
Abstract
Consider two types of instructions for manipulating disjoint sets. FIND(x) computes the name of the (unique) set containing element x. UNION(A,B,C) combines sets A and B into a new set named C. We examinee a known algorithm for implementing sequences of these instructions. We show that if f(n) is the maximum time required by any sequence of n instructions, $k_{1} n \alpha (n) \leq f(n) \leq k_{2} n \log^{*}(n)$ for some constants $k_{1}$ and $k_{2}$, where $\log^{*}(n) = \min\{i|\log^{i}(n) \leq 1\}$ and $\alpha(n)$ is a recursively defined function which satisfies $\alpha(n) \rightarrow \infty$ as $n \rightarrow \infty$. Thus the set union algorithm is $O(n \log^{*}(n))$ but not $O(n)$. Keywords and phrases: algorithm, complexity, equivalence, partition, set union, tree.
Date Issued
1972-11Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-148
Type
technical report