Course contentsShow
← Computer Science
Lesson 1019 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Prim's Algorithm: Time Complexity Analysis

Analyze Prim's time complexity with different data structures: O(V²) with arrays or O((V+E) log V) with binary heaps.

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.