Union Find Disjoint Set Data Structure in DSA Typescript - 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 groups and checking if elements belong together.

How does the time needed change as we add more elements and connections?

Scenario Under Consideration

Analyze the time complexity of the following Union Find operations.

class UnionFind {
  parent: number[];
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(a: number, b: number): void {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) this.parent[rootB] = rootA;
  }
}
    

This code creates groups of connected elements and finds which group an element belongs to, using path compression.

Identify Repeating Operations

Look at the main repeated actions:

• Primary operation: The find method, which follows parent links up to the root.
• How many times: Each union calls find twice; many find calls happen during unions and checks.

How Execution Grows With Input

As we add more elements and unions, the time per operation grows very slowly.

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

Pattern observation: The steps grow very slowly, almost like a flat line, thanks to path compression.

Final Time Complexity

Time Complexity: O(α(n)) per operation

This means each find or union runs in almost constant time, where α(n) is a very slow-growing function.

Common Mistake

[X] Wrong: "Each find operation takes linear time because it may follow many parents."

[OK] Correct: Path compression flattens the structure, so repeated finds become very fast, not linear.

Interview Connect

Understanding Union Find's time complexity shows you can handle efficient grouping problems, a common skill in coding challenges.

Self-Check

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