Prim’s algorithm starts by selecting the least weight edge from one node. In a complete network there are (n - 1) edges from each node.
At step 1 this means that there are (n - 1) - 1 comparisons to make.
Having made the first comparison and selection there are (n - 2) unconnected nodes, with a edges joining from each of the two nodes already selected. This means that there are (n - 2) - 1 comparisons that need to be made.
Carrying on this argument results in the following expression for the number of comparisons that need to be made to complete the minimum spanning tree: ((n - 1) - 1) + (2(n - 2) - 1) + (3(n - 3) - 1) + \dotsc + ((n - 1)(n - (n - 1)) - 1)
The result is that Prim’s algorithm has cubic complexity.
Can I ask why it is (n-1)-1 comparisons for first node? So, for instance, if we have a 5 node complete graph and picture it in a matrix (let’s say the nodes are named A to E) wouldn’t starting at A mean I need to check four edges down that column – or are you imagining picking one of those edges and comparing it in size to the other 3 that exist there, essentially?
Hi Marguerite,
Your example of picking an edge and comparing with the others is the one. Let’s say we have these weights:
It does not matter which edge you look at first, so let’s choose AB.
With those 4 nodes we need only 3 comparisons to be certain of the least weight, but we do have to consider all 4 values.