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 TT?

Solution

  • Naive approach: Try all edges O(M)\Omicron(M).

  • Better approach: Keep all the edges that have one endpoint in TT in a (min-heap) Priority Queue and remove the best (min) at each iteration: O(lg⁡M)\Omicron(\lg M)

Exercise Based on your answer to the previous question, analyze the asymptotic complexity of Prim's algorithm.

Solution

Runtime: O(Mlg⁡M)\Omicron(M \lg M) – with O(M)\Omicron(M) auxiliary space.

OperationFrequencyCost per operation
pq.remove()O(M)\Omicron(M)O(lg⁡M)\Omicron(\lg M)
pq.insert()O(M)\Omicron(M)O(lg⁡M)\Omicron(\lg M)

Note: you might have to remove multiple edges until you find one with only one endpoint in TT. That's why remove's frequency is MM, not NN.

Considering M∈O(N2)M\in \Omicron(N^2), we have O(Mlg⁡M)≡O(Mlg⁡N2)≡O(Mlg⁡N)\Omicron(M \lg M) \equiv \Omicron(M \lg N^2) \equiv \Omicron(M \lg N) for simple graphs.