Complexity Analysis

With both optimizations, find and union run in $O(\alpha(n))$ amortized time. $\alpha(n)$ is the inverse Ackermann function.

It grows slowly:

• $\alpha(10^{80}) \leq 4$ (there are about $10^{80}$ atoms in the universe)

For all practical purposes, $\alpha(n)$ is constant.

You can safely assume Union-Find operations are $O(1)$. Space complexity is $O(n)$ for the parent and rank/size arrays.

This makes Union-Find efficient:

• $m$ operations on $n$ elements: $O(m \cdot \alpha(n)) \approx O(m)$
• Much faster than recomputing connectivity with BFS/DFS

The proof of this bound is complex and involves potential functions. For competitive programming, remember: it's effectively constant time.