Path Compression in Union Find in DSA Typescript - 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 using path compression in Union Find.

How does the time to find the root change as we do more operations?

Scenario Under Consideration

Analyze the time complexity of the following find function with path compression.

function find(parent: number[], x: number): number {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}
    

This code finds the root of element x and flattens the path to speed up future finds.

Identify Repeating Operations

Look for loops or recursion that repeat work.

• Primary operation: Recursive calls to find following parent links.
• How many times: Up to the height of the tree before compression.

How Execution Grows With Input

Initially, the tree can be tall, so find may take many steps. But path compression flattens it fast.

Input Size (n)	Approx. Operations per find
10	About 2-3 steps after some finds
100	About 4-5 steps initially, fewer after compression
1000	Starts higher but quickly flattens to near 1 step

Pattern observation: The steps grow very slowly and almost stay constant after many finds.

Final Time Complexity

Time Complexity: O(α(n))

This means each find runs in almost constant time, where α(n) is a very slow growing function (the inverse Ackermann function).

Common Mistake

[X] Wrong: "Find always takes time proportional to the height of the tree."

[OK] Correct: Path compression flattens the tree so future finds become much faster, making the average cost almost constant.

Interview Connect

Understanding path compression's time complexity shows you can analyze clever optimizations that make algorithms very efficient in practice.

Self-Check

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