Borůvka's algorithm can be shown to run in time [[Big O notation|O]](''E''log ''V''), where ''E'' is the number of edges, and ''V'' is the number of vertices in ''G''.
Other algorithms for this problem include [[Prim's algorithm]] (actually discovered by [[Vojtěch JarnikJarník]]) and [[Kruskal's algorithm]]. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized version of Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected <math>O(E)</math> time. The best known minimum spanning tree algorithm by [[Bernard Chazelle]] is based on Borůvka's and runs in O(''E'' α(V)) time, where α is the inverse of the [[Ackermann function]].
