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-11#####
**Publisher**

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