Question: If you have n elements and perform m union operations, what is the amortized time complexity of each operation in a Disjoint Set Union with path compression and union by rank?

Options:

1. O(1)
2. O(log n)
3. O(n)
4. O(α(n))

Correct Answer: O(α(n))

Solution:

The amortized time complexity of each operation in a Disjoint Set Union with path compression and union by rank is O(α(n)), where α is the inverse Ackermann function.