Prim's Algorithm: Analysis
- Compare various approaches to finding the next min edge and the resulting time/space tradeoffs between them for Prim's algorithm.
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 $\Omicron(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: $\Omicron(\lg M)$
Exercise Based on your answer to the previous question, analyze the asymptotic complexity of Prim's algorithm.
Solution
Runtime: $\Omicron(M \lg M)$ – with $\Omicron(M)$ auxiliary space.
| Operation | Frequency | Cost per operation |
|---|---|---|
pq.remove() | $\Omicron(M)$ | $\Omicron(\lg M)$ |
pq.insert() | $\Omicron(M)$ | $\Omicron(\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 \Omicron(N^2)$, we have $\Omicron(M \lg M) \equiv \Omicron(M \lg N^2) \equiv \Omicron(M \lg N)$ for simple graphs.