Minimum spanning tree (Prim's) in Data Structures Theory - Time & Space Complexity

Time Complexity: Minimum spanning tree (Prim's)

O(n^2)

Understanding Time Complexity

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

Specifically, how does the work increase when the number of nodes and edges increases?

Scenario Under Consideration

Analyze the time complexity of the following Prim's algorithm code snippet.

function primMST(graph) {
  let mstSet = new Set();
  let key = Array(graph.length).fill(Infinity);
  key[0] = 0;
  for (let count = 0; count < graph.length; count++) {
    let u = minKey(key, mstSet);
    mstSet.add(u);
    for (let v = 0; v < graph.length; v++) {
      if (graph[u][v] && !mstSet.has(v) && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return key;
}
    

This code finds the minimum spanning tree by repeatedly adding the closest vertex not yet in the tree.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The outer loop runs once for each vertex to add it to the MST.
• How many times: For each vertex, the inner loop checks all vertices to update keys.

How Execution Grows With Input

As the number of vertices (n) grows, the algorithm checks all vertices for each addition to the MST.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows roughly with the square of the number of vertices.

Final Time Complexity

Time Complexity: O(n^2)

This means if you double the number of vertices, the time needed roughly quadruples.

Common Mistake

[X] Wrong: "Prim's algorithm always runs in linear time because it just adds one vertex at a time."

[OK] Correct: Each addition requires checking all vertices to find the minimum edge, so the total work grows faster than just the number of vertices.

Interview Connect

Understanding how Prim's algorithm scales helps you explain your choices and shows you grasp how graph size affects performance.

Self-Check

"What if we used a priority queue (min-heap) to select the next vertex? How would the time complexity change?"