In Kruskal’s algorithm we need to find edge with the lowest weight at each step. Taking the worst case of a complete network there will be _nC^2 edges, which is equal to \frac{1}{2}[n(n + 1)] possible edges. Inspecting each edge to determine the one with the lowest weight is the most time consuming job so the number of inspections to complete the problem will give an indication of the complexity of the algorithm.

In the first round of inspections, all of the edges need to be inspected and compared. There will be \frac{1}{2}[n(n + 1)] - 1 comparisons to make.

In the second round of inspections, all of the edges, except the one already selected, need to be inspected and compared. There will be \frac{1}{2}[n(n + 1)] - 2 comparisons to make.

In a spanning tree for a network with n nodes, there will be (n - 1) edges that will have to be selected. This would require the following number of comparisons to be made in total:
{\frac{1}{2}[n(n + 1)] - 1} + {\frac{1}{2}[n(n + 1)] - 2} + {\frac{1}{2}[n(n + 1)] - 3} + \dotsc + {\frac{1}{2}[n(n + 1)] - (n - 1)}

After messing about with all of the algebra you discover that this can also be written as: \frac{1}{2}n(n - 1)(n - 2) = \frac{1}{2}(n^3 - 3n^2 + 2n). It follows that Kruskal’s algorithm has cubic complexity.