Minimum Spanning Tree Kruskal's Algorithm in DSA C - 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 size grows.

Specifically, how does the number of edges and vertices affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Kruskal's Algorithm main steps
sort(edges, edges + E, compare);
for (int i = 0; i < E; i++) {
  if (findSet(edges[i].u) != findSet(edges[i].v)) {
    unionSet(edges[i].u, edges[i].v);
    mst_weight += edges[i].weight;
  }
}

This code sorts all edges by weight and then adds edges to the MST if they connect different sets.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting all edges and iterating through them.
• How many times: Sorting takes about E log E steps; the loop runs E times.
• Union-Find operations: Each union or find operation is almost constant time due to path compression.

How Execution Grows With Input

As the number of edges (E) and vertices (V) grow, sorting edges takes more time, and we check each edge once.

Input Size (E)	Approx. Operations
10	About 10 * log 10 ≈ 33 steps
100	About 100 * log 100 ≈ 664 steps
1000	About 1000 * log 1000 ≈ 9966 steps

Pattern observation: The work grows a bit faster than the number of edges because of sorting, but union-find operations stay very fast.

Final Time Complexity

Time Complexity: O(E log E)

This means the time grows mostly with sorting edges, and the rest of the steps add only small extra time.

Common Mistake

[X] Wrong: "The algorithm takes O(V^2) time because it checks all pairs of vertices."

[OK] Correct: Kruskal's algorithm works mainly with edges, not all vertex pairs, and sorting edges dominates the time, not checking all pairs.

Interview Connect

Understanding Kruskal's time complexity shows you can analyze sorting and efficient data structures like union-find, skills valuable in many algorithm problems.

Self-Check

"What if we used a different data structure for union-find without path compression? How would the time complexity change?"