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

Time Complexity: Minimum Spanning Tree Prim's Algorithm

O(n²)

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 size grows.

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

Scenario Under Consideration

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

function primMST(graph: number[][]): number[] {
  const n = graph.length;
  const key = Array(n).fill(Infinity);
  const mstSet = Array(n).fill(false);
  key[0] = 0;

  for (let count = 0; count < n - 1; count++) {
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && (u === -1 || key[v] < key[u])) u = v;
    }
    mstSet[u] = true;

    for (let v = 0; v < n; v++) {
      if (graph[u][v] !== 0 && !mstSet[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return key;
}
    

This code finds the minimum spanning tree weights for a graph represented by an adjacency matrix.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: The outer loop runs once for each node (n times).
• Inside it: A loop to find the minimum key value among nodes not yet in MST (runs n times).
• Another loop: Updates keys for neighbors of the chosen node (runs n times).
• Dominant work: The nested loops inside the outer loop, each running up to n times, dominate the cost.

How Execution Grows With Input

As the number of nodes (n) grows, the loops multiply work roughly by n * n.

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

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

Final Time Complexity

Time Complexity: O(n²)

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

Common Mistake

[X] Wrong: "Prim's algorithm always runs in linear time O(n)."

[OK] Correct: The nested loops cause the time to grow with the square of nodes, not just linearly.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why certain data structures can improve performance.

Self-Check

"What if we used a priority queue (min-heap) to select the minimum key instead of scanning all nodes? How would the time complexity change?"