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.