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) ?
Best Answer
At each step you have to find for given component an edge with smallest weight connecting it to different component. At worst case you have to visit every edge at every iteration ->
|E|.