Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript - Time & Space Complexity

Time Complexity: Minimum Spanning Tree Kruskal's Algorithm

O(E log E)

Understanding Time Complexity

We want to understand how the time needed to find a minimum spanning tree using Kruskal's algorithm changes as the graph grows.

Specifically, how the number of edges and vertices affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following Kruskal's algorithm snippet.

function kruskal(edges: [number, number, number][], verticesCount: number) {
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array(verticesCount).fill(0).map((_, i) => i);
  const rank = Array(verticesCount).fill(0);

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

  function union(a: number, b: number): boolean {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return false;
    if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
    else if (rank[rootB] < rank[rootA]) parent[rootB] = rootA;
    else {
      parent[rootB] = rootA;
      rank[rootA]++;
    }
    return true;
  }

  const mst = [];
  for (const [u, v, w] of edges) {
    if (union(u, v)) mst.push([u, v, w]);
  }
  return mst;
}
    

This code sorts edges by weight, then adds edges to the MST if they connect different sets, using union-find to avoid cycles.

Identify Repeating Operations

Look for loops and repeated calls that take most time.

• Primary operation: Sorting all edges by weight.
• How many times: Sorting runs once on all edges, which is E edges.
• Secondary operation: The loop over all edges to try union operations.
• Union-Find operations: Each union or find runs almost constant time, but called up to E times.

How Execution Grows With Input

As the number of edges (E) and vertices (V) grow, the sorting step dominates.

Input Size (E, V)	Approx. Operations
10 edges, 5 vertices	About 10 log 10 = 33 operations for sorting + 10 union-find calls
100 edges, 50 vertices	About 100 log 100 = 664 operations for sorting + 100 union-find calls
1000 edges, 500 vertices	About 1000 log 1000 = 9965 operations for sorting + 1000 union-find calls

Pattern observation: The sorting grows faster than the union-find calls, roughly proportional to E times log E.

Final Time Complexity

Time Complexity: O(E log E)

This means the time grows mostly with sorting the edges, which depends on the number of edges times the logarithm of that number.

Common Mistake

[X] Wrong: "The union-find operations take as much time as sorting."

[OK] Correct: Union-find operations are almost constant time due to path compression and ranking, so sorting dominates the total time.

Interview Connect

Understanding Kruskal's time complexity shows you can analyze algorithms that combine sorting and efficient data structures, a key skill in many coding challenges.

Self-Check

"What if the edges were already sorted? How would that affect the time complexity?"