Runtime after improvements!

  • Identify the amortized runtime of union-find operations.

If implemented with Union-by-size and Path Compression:

  • practically keeps the tree almost flat
  • makes the operations work in O(lg⁡∗N)\Omicron(\lg^* N)

lg⁡∗N\lg^* N (read: Iterated logarithm of NN) is the number of times one needs to apply lg⁡\lg to NN to get a value less than or equal to 11.

In practice, one could think of it to be almost O(1)\Omicron(1) since it exceeds 55 only after it has reached 2655362^{65536}.

Aside: The proof of the above running time is beyond the scope of this course. The Union-Find data structure was invented in 1964. The running time above was proved in 1973 (by Hopcroft and Ullman — see their paper).