2
$\begingroup$

I'm studying about time complexity of Kruskal's algorithm.

But there are two opinions to express time complexity as $O(|E|\lg|E|), O(|E|\lg|V|)$.

I know $O(|E|\lg|E|)$ is occurred from sorting by non-decreasing order of vertices.

But I don't understand of $O(|E|\lg|V|)$. This answer explains by $|E|\le|V|^2$, however from my knowledge, maximum number of vertices in undirected graph is $|E|\le\frac{|V|(|V|-1)}{2}$.

What is right time complexity for Kruskal's algorithm?

$\endgroup$
9
  • $\begingroup$ For a connected graph, the two running times you state are equivalent. $\endgroup$ May 22, 2018 at 5:18
  • $\begingroup$ @YuvalFilmus That is I already said in the post. $\endgroup$
    – molamola
    May 22, 2018 at 5:26
  • $\begingroup$ So both running times are correct. $\endgroup$ May 22, 2018 at 5:51
  • $\begingroup$ @YuvalFilmus My question is why connected graph of undirected graph has maximum number of vertices as $|V|^2$. $\endgroup$
    – molamola
    May 22, 2018 at 6:04
  • $\begingroup$ The maximum number of edges is $\binom{|V|}{2}$. $\endgroup$ May 22, 2018 at 6:24

1 Answer 1

3
$\begingroup$

Kruskal's algorithm is only applied to connected graphs. These have at least $|V|-1$ edges. On the other hand, the complete graph has $\binom{|V|}{2}$ edges, and so $$ |V|-1 \leq |E| \leq \binom{|V|}{2}. $$ The left-hand side is $\Omega(|V|)$ and the right-hand side is $O(|V|^2)$. Therefore $\log |E| = \Theta(\log |V|)$. For this reason, the two quoted running times $O(|E| \log |E|)$ and $O(|E| \log |V|)$ are completely identical — on connected graphs, an algorithm has running time $O(|E| \log |E|)$ iff it has running time $O(|E| \log |V|)$.

$\endgroup$
9
  • $\begingroup$ Thank you for your excellent answer! Then, what is the answer of binomial coefficent? Is it almost $|V|^2$ and why? If it bothers you, just skip it. It is enough to your sincere answer. $\endgroup$
    – molamola
    May 22, 2018 at 14:39
  • 1
    $\begingroup$ The binomial coefficient is roughly $|V|^2/2$. Its exact value is $|V|(|V|-1)/2$. $\endgroup$ May 22, 2018 at 14:41
  • 1
    $\begingroup$ Yes, these inequalities are valid. $\endgroup$ May 22, 2018 at 14:43
  • 1
    $\begingroup$ Follow your course of studies, and eventually you will know more. At any rate, this is not for the comment section. $\endgroup$ May 22, 2018 at 14:52
  • 1
    $\begingroup$ No, you'd have to write a new post. $\endgroup$ May 22, 2018 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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