In a Disjoint Set Union (DSU) data structure, what is the nearly-constant time complexity achieved by using both union-by-rank and path compression?
Show answer
O(α(n))
The function α(n) is the inverse Ackermann function, which grows extremely slowly; for all practical values of n, α(n) is less than 5. This makes DSU operations effectively constant time in practice.
Also asked as:
- What is the amortized time complexity per DSU operation when both path compression and union-by-rank are implemented?