Why it is nearly O(1)

With union by rank and path compression together, one find can still take log₂ n steps. But over a long run of operations, the average is so small that it is at most 4 or 5 for any n that will ever be used. This lesson shows the numbers and the idea of the proof.

Cost over many operations

Path compression makes a slow find speed up the finds after it. So the right question is not “how slow can one find be?” but “how much do m operations cost together?”. The total divided by m is called the amortised cost of an operation: the cost shared out over the whole run, as BIGO-7 did for appending to a list. It is a guarantee about every run of operations, not an average over random inputs.

What the numbers show

The figure shows numbers measured by a short program: the average number of parent steps per operation, for growing n, and for four versions of union-find: with neither rule, with union by rank only, with path compression only, and with both.

• Chain of unions. With no rule, the path grows to length n − 1 and the average grows with n: thousands of steps per operation. Either rule alone fixes this order of operations.
• Equal unions. This order makes rank-only trees as tall as the proof of lesson 2 allows, so rank alone grows like log₂ n. With compression, each long find flattens its path, and the average stays below 2.

The iterated logarithm

The first proof of the bound (by Hopcroft and Ullman, 1973) uses a function that grows extremely slowly. log* n (“log star”) is the number of times you must take log₂, one after another, before the result is 1 or less. The third variant of the figure counts it for n = 2⁶⁵⁵³⁶ (2 to the power 65,536): 5 times. For any n that fits in a computer, log* n ≤ 5: log* n is at most 5.

The proof sketch has three facts and one way of counting.

1. Ranks go up along every path. A parent always has a higher rank than its child. Union puts a lower rank under a higher one (or raises the top one), and compression only gives a node a new parent further up the same path, which has an even higher rank.
2. High ranks are rare. By lesson 2, a node that reached rank r had at least 2^r elements below it at that moment, and two nodes of the same rank never share those elements. So at most n / 2^r nodes ever have rank r.
3. Put the ranks into groups whose ends grow as fast as possible: ranks 0 to 1, then 2, then 3 to 4, then 5 to 16, then 17 to 65,536. Each group ends at 2 to the power of the previous end. There are at most log* n + 1 groups.

Now count the parent steps of one find. A step from a node whose parent is in a higher group, or whose parent is the root, is paid by the find: there are at most log* n + 2 such steps, because ranks only go up along the path. Every other step is paid by the node itself. Each time a node pays, compression gives it a new parent with a higher rank in the same group, or in a higher one. A group from rank k + 1 to 2^k lets a node pay at most 2^k times before its parent leaves the group, and after that the find pays for it. By fact 2, at most n / 2^k nodes have a rank in that group, so the nodes of one group pay at most n steps in all, and all groups together at most n · (log* n + 1). Add the finds’ own share, m · (log* n + 2), and the bound follows.

The exact bound

In 1975 Robert Tarjan proved a sharper bound: O(m · α(n)), where α is the inverse Ackermann function. The Ackermann function grows faster than any tower of powers, so its inverse grows even more slowly than log* n: α(n) is at most 4 for every n below a number far too large to write down. He also proved that no method of this kind can do better, so the bound is exact.

In practice, treat both find and union as O(1): a constant that is at most about 4 or 5. That is what “nearly O(1)” means.