The paper by Robert Endre Tarjan analyzes an algorithm for manipulating disjoint sets, specifically focusing on the efficiency of a set union algorithm. The algorithm uses two operations: FIND(x) to find the set containing element x, and UNION(A, B, C) to combine sets A and B into a new set C. The analysis examines the maximum time required for a sequence of m FINDs and n-1 intermixed UNIONs, denoted as \( t(m, n) \). Tarjan shows that \( t(m, n) \) can be bounded by \( k_1 \alpha(m, n) \leq t(m, n) \leq k_2 \alpha(m, n) \), where \( \alpha(m, n) \) is related to a functional inverse of Ackermann's function and grows very slowly. This means that \( t(m, n) \) is \( o(m \log^* n) \) but not \( O(m) \). The paper also discusses the use of collapsing and weighted union rules, which can improve the efficiency of the algorithm. The author provides upper and lower bounds on the time complexity using these rules and proves that the algorithm's worst-case running time is \( O(m \alpha(m, n)) \). The bound is tight within a constant factor. Finally, the paper concludes with a discussion on the optimality of the algorithm and open problems, including the possibility of a linear-time algorithm for the online set union problem.The paper by Robert Endre Tarjan analyzes an algorithm for manipulating disjoint sets, specifically focusing on the efficiency of a set union algorithm. The algorithm uses two operations: FIND(x) to find the set containing element x, and UNION(A, B, C) to combine sets A and B into a new set C. The analysis examines the maximum time required for a sequence of m FINDs and n-1 intermixed UNIONs, denoted as \( t(m, n) \). Tarjan shows that \( t(m, n) \) can be bounded by \( k_1 \alpha(m, n) \leq t(m, n) \leq k_2 \alpha(m, n) \), where \( \alpha(m, n) \) is related to a functional inverse of Ackermann's function and grows very slowly. This means that \( t(m, n) \) is \( o(m \log^* n) \) but not \( O(m) \). The paper also discusses the use of collapsing and weighted union rules, which can improve the efficiency of the algorithm. The author provides upper and lower bounds on the time complexity using these rules and proves that the algorithm's worst-case running time is \( O(m \alpha(m, n)) \). The bound is tight within a constant factor. Finally, the paper concludes with a discussion on the optimality of the algorithm and open problems, including the possibility of a linear-time algorithm for the online set union problem.