With both optimizations, find and union run in amortized time. is the inverse Ackermann function.
It grows slowly:
- (there are about atoms in the universe)
For all practical purposes, is constant.
You can safely assume Union-Find operations are . Space complexity is for the parent and rank/size arrays.
This makes Union-Find efficient:
- operations on elements:
- 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.