The expected complexity of Prim's minimum spanning tree algorithm

We study the expected performance of Prim's minimum spanning tree (MST) algorithm implemented using ordinary heaps. We show that this implementation runs in linear or almost linear expected time on a wide range of graphs. This helps to explain why Prim's algorithm often beats MST algorithms which have better worst-case run times. Specifically, we show that if we start with any n node m edge graph and randomly permute its edge weights, then Prim's algorithm runs in expected O(m + n loan log(2m/n)) time. Note that O(m + n loan log(2m/n)) = 0(m) when in 0 (n log n log log n). We extend this result to show that the same expected run times apply even when an adversary can select the weights of m/log n edges and the possible weights of the remaining edges (which are then randomly assigned). (C) 2002 Elsevier Science B.V. All rights reserved.