Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?
The best prime complexity I have found is $O(|V|^2)$, and the complexity of the Kruskal algorithm is $O(|E|\cdot \log(|E|))= O(|V|^2 \cdot \log(|V|))$.
Any ideas for how to improve the time complexity so that we get something more efficient than $|V|^2$?
Since it is a complete undirected graph, the number of edges are $\Theta(n^{2})$, where $n = |V|$. In order to find the MST, you must find the edge of minimum weight among all the given edges since it is always a part of the Minimum Spanning Tree. Since, the lower bound of finding the minimum among $N$ elements is $\Omega(N)$. Therefore, you can not do better than $\Omega(n^{2})$ if the graph is complete.