Union Find Disjoint Set Data Structure in DSA C - Time & Space Complexity

Time Complexity: Union Find Disjoint Set Data Structure

O(α(n))

Understanding Time Complexity

We want to understand how fast the Union Find data structure works when connecting and checking groups.

How does the time needed change as we add more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find with path compression
int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// Union by rank
void unionSets(int parent[], int rank[], int a, int b) {
    a = find(parent, a);
    b = find(parent, b);
    if (a != b) {
        if (rank[a] < rank[b])
            parent[a] = b;
        else if (rank[b] < rank[a])
            parent[b] = a;
        else {
            parent[b] = a;
            rank[a]++;
        }
    }
}
    

This code finds the group leader of an element and merges two groups efficiently.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive find function that follows parent links to find the root.
• How many times: Each find call may traverse up the tree, but path compression flattens it over time.

How Execution Grows With Input

Initially, finding a root may take longer if trees are tall, but path compression and union by rank keep trees shallow.

Input Size (n)	Approx. Operations per find/union
10	About 4-5 steps or less
100	About 5-6 steps or less
1000	About 6-7 steps or less

Pattern observation: The steps grow very slowly, almost constant, even as input grows large.

Final Time Complexity

Time Complexity: O(α(n))

This means each operation takes almost constant time, where α(n) is a very slow growing function.

Common Mistake

[X] Wrong: "Each find or union takes linear time because it may traverse many parents."

[OK] Correct: Path compression and union by rank keep trees very flat, so operations are almost constant time, not linear.

Interview Connect

Understanding this complexity shows you can handle efficient grouping problems, a common skill in many coding challenges.

Self-Check

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