On the Efficiency of a Good but Not Linear Set Union Algorithm

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