Questions: Union-Find (Disjoint Set Union)

Question 1

A developer implements union-find with union by rank but forgets to add path compression. What is the amortized time complexity per operation?

• A. O(α(n)) — essentially constant, the same as with both optimizations
• B. O(log n) — better than naive O(n) but worse than using both optimizations together
• C. O(n) — linear, the same as the naive implementation without any optimization
• D. O(1) — union by rank alone is sufficient for constant-time performance

Answer: (B)

Union by rank alone bounds tree height at O(log n), so find operations take O(log n) in the worst case — significantly better than naive O(n) but far from near-constant. The near-O(1) amortized bound of O(α(n)) requires *both* optimizations working together. Path compression alone also gives roughly O(log n) amortized. Only the combination of union by rank AND path compression achieves the nearly-constant O(α(n)) bound.

Question 2

In Kruskal's minimum spanning tree algorithm, union-find is used to evaluate each candidate edge. What specific question does the find operation answer?

• A. Whether the edge has the minimum weight among all remaining candidate edges
• B. Whether the two endpoints of the edge are currently in the same connected component
• C. Whether the edge forms the shortest path between its two endpoints
• D. Whether the edge's weight exceeds the average weight of edges already added to the tree

Answer: (B)

Kruskal's algorithm adds edges in sorted order by weight, skipping any edge that would form a cycle. An edge creates a cycle if and only if its two endpoints are already in the same connected component — i.e., they share the same representative in the union-find structure. The find operation returns each endpoint's root; if both roots are the same, the edge is rejected. If they differ, the edge is added and the two components are merged via union.

Question 3

Path compression during a find operation changes which element is the representative (root) of the set.

• T. True
• F. False

Answer: False

Path compression only shortens the path from each traversed node to the root — it does not change which node is the root. Every node along the path from the queried element to the root is redirected to point directly at the root, making future finds on those nodes faster. But the root (the representative) remains unchanged. This is why path compression is safe: it restructures the internal tree for efficiency without altering the logical partition into sets.

Question 4

The near-O(1) amortized time bound for union-find operations requires both path compression and union by rank; either optimization alone gives a weaker guarantee.

• T. True
• F. False

Answer: True

Union by rank alone limits tree height to O(log n). Path compression alone reduces depths but can still encounter tall trees before compression kicks in. The combination achieves O(α(n)) amortized, where α is the inverse Ackermann function — effectively constant for any practical input size (α(n) ≤ 4 for n up to roughly 10^80). Applying only one of the two optimizations yields at best O(log n) amortized.

Question 5

Why does path compression speed up future find operations, even though it doesn't change which element is the representative of a set?

Model answer: When find traverses a chain of parent pointers to reach the root, path compression redirects every node along that chain to point directly at the root. On future find calls for any of those nodes, the traversal reaches the root in a single step instead of following the entire chain again. The representative (root) doesn't change — only the internal tree structure is flattened. Because future operations are dramatically shorter, the total cost of many operations is amortized to nearly O(1) per operation.

Path compression is a rare case of an optimization that pays for itself over time: the initial find might traverse a long chain, but it flattens that chain as it goes, making all subsequent finds on those nodes essentially free. This amortized analysis — where a costly operation makes future operations cheap — is the core reason union-find with both optimizations achieves such strong theoretical guarantees in practice.