Prim's Algorithm: Analysis
Exercise Based on your understanding of Prim's algorithm, how can we efficiently implement the step which involves finding min-weight edge with one endpoint in $T$?
Solution
-
Naive approach: Try all edges $O(M)$.
-
Better approach: Keep all the edges that have one endpoint in $T$ in a (min-heap) Priority Queue and remove the best (min) at each iteration: $O(\lg M)$
Exercise Based on your answer to the previous question, analyze the asymptotic complexity of Prim's algorithm.
Solution
Runtime: $O(M \lg M)$ – with $O(M)$ auxiliary space.
| Operation | Frequency | Cost per operation |
|---|---|---|
pq.remove() | $O(M)$ | $O(\lg M)$ |
pq.insert() | $O(M)$ | $O(\lg M)$ |
Note: you might have to remove multiple edges until you find one with only one endpoint in $T$. That's why remove's frequency is $M$, not $N$.
Considering $M\in O(N^2)$, we have $O(M \lg M) \equiv O(M \lg N^2) \equiv O(M \lg N)$ for simple graphs.