Path Compression in Union Find in DSA C - Time & Space Complexity

Time Complexity: Path Compression in Union Find

O(α(n))

Understanding Time Complexity

We want to understand how fast the "find" operation runs when we use path compression in Union Find.

Specifically, how does the time grow as we have more elements and unions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}
    

This code finds the root parent of element x and compresses the path by making x point directly to the root.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to find until the root is reached.
• How many times: At most the height of the tree representing the set.

How Execution Grows With Input

Initially, trees can be tall, so find may take longer. But path compression flattens trees over time.

Input Size (n)	Approx. Operations per find
10	About 2-3 steps after some finds
100	About 4-5 steps after many finds
1000	About 5-6 steps after many finds

Pattern observation: The number of steps grows very slowly, almost constant for practical sizes.

Final Time Complexity

Time Complexity: O(α(n))

This means each find runs in almost constant time, where α(n) is the inverse Ackermann function, which grows extremely slowly.

Common Mistake

[X] Wrong: "Path compression makes find run in constant time always."

[OK] Correct: Initially, find can take longer if trees are tall, but path compression quickly flattens them, making future finds very fast.

Interview Connect

Understanding path compression's time complexity shows you how clever tweaks make algorithms efficient in practice, a skill valued in problem solving.

Self-Check

"What if we removed path compression? How would the time complexity of find change?"