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

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.