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.