Prim's Algorithm: Time Complexity Analysis
You'll learn: How the choice of data structure dramatically affects Prim's algorithm runtime, from quadratic to near-linear performance.
Why Data Structures Matter
Prim's algorithm repeatedly finds the minimum-weight edge connecting the growing MST to a new vertex, then updates neighboring edge weights. How efficiently you perform these operations determines overall speed.
Array-Based Implementation: O(V²)
Using a simple array to track minimum edge weights to each vertex:
- Finding minimum: Scan all V vertices each iteration → O(V) per iteration
- V iterations (one per vertex added) → O(V²) total
- Edge updates: After adding a vertex, update its neighbors → O(E) total across all iterations
Combined: O(V²), since the V² dominates even when we add O(E).
Best for: Dense graphs where E ≈ V², making this actually efficient.
Binary Heap Priority Queue: O((V + E) log V)
Using a min-heap (binary heap) to store vertices by edge weight:
- Extract minimum: O(log V) per extraction × V extractions = O(V log V)
- Edge updates (decrease-key): Each of E edges might trigger an update at O(log V) = O(E log V)
Combined: O((V + E) log V)
Best for: Sparse graphs where E << V², making the logarithmic factor worthwhile.
The Trade-off
Think of it like searching for the smallest item in a collection. With an unsorted array, you must check everything (slow find, fast update). With a heap, you get organized access (fast find, slower update). The graph's density determines which overhead pays off.
Key Takeaway: Prim's runs in O(V²) with simple arrays or O((V + E) log V) with binary heaps—choose based on whether your graph is dense or sparse.