A question on the computational complexity of Boruvka's algorithm

1.8k Views Asked by At

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm).

On the page you would see once you clicked the hyperlink, it is mentioned that the computational complexity of Boruvka's Algorithm is $O(|E| \cdot \log(|V|) )$, where $|E|$ is the number of edges in the graph, and $|V|$ is the number of vertices in the graph.

I understand the $ \log(|V|) $ part. In the worst case, the number components $T$ of the graph after the iteration is only half as much as the number of components $T$ before the iteration. So the computational complexity is actually $\log_{2} (|V| ) $.

However, I don't understand the $ |E| $ part. Why does it, in the worst-case scenario, take $|E|$ steps to complete the algorithm? How come it is exactly the number of edges (in the worst case) ?