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

Time Complexity: Minimum Spanning Tree Prim's Algorithm

O(V^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 number of steps grow when the graph has more nodes and edges?

Scenario Under Consideration

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

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
}
    

This code finds the minimum spanning tree of a graph using Prim's algorithm with an adjacency matrix.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The outer loop runs once for each vertex (V times).
• Nested operation: Inside, the inner loop checks all vertices to update keys (V times per outer loop).
• Dominant operation: The nested inner loop checking all vertices dominates the time.

How Execution Grows With Input

As the number of vertices (n) grows, the algorithm does more work:

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

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

Final Time Complexity

Time Complexity: O(V2)

This means if the number of vertices doubles, the time to run the algorithm roughly quadruples.

Common Mistake

[X] Wrong: "Prim's algorithm always runs in linear time because it just picks edges one by one."

[OK] Correct: The algorithm checks all vertices repeatedly to find the minimum key, which takes more time as the graph grows, especially with an adjacency matrix.

Interview Connect

Understanding how Prim's algorithm scales helps you explain your choices clearly and shows you know how to handle graphs efficiently in real problems.

Self-Check

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