0
$\begingroup$

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?

$\endgroup$
1
$\begingroup$

Almost linear in term of the number of edges of the graph.

More specifically, here is the quote from Wikipedia entry on Kruskal's algorithm.

Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in $O(E \,\alpha(V))$ time, where α is the extremely slowly growing inverse of the single-valued Ackermann function.

Here $E$ stands for the number of edges in the graph and $V$ stands for the number of vertices in the graph. In fact, $\alpha(n)$ is less than 5 for any practical input size $n$, since $\alpha$ is the inverse of the growing function $f$ and $f(1)=3$, $f(2)=7$,$f(3)=61$, $f(4)=2^{2^{2^{2^{16}}}}-3$, a number whose number of digits is a number whose number of digits is 19727 (all fractional parts ignored). In other words, even if $n$ has trillions of trillions of digits, $\alpha(n)$ is still 4.

Please note in computer science, this factor $a(V)$, however slowly grows, represents a real barrier to achieve a linear algorithm even after the edges have been sorted by weight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.