1

Here is a snippet of my pseudo code to find the MST of each Strong Connect Component (SCC) given a graph, G:

Number of SCC, K <- apply Kosaraju's algorithm on Graph G O(V + E)

Loop through K components:
 each K components <- apply Kruskal's algorithm

According to what I have learnt, Kruskal's algorithm run in O(E log V) time.

However, I am unsure of the worst case time complexity of the loop. My thought is that the worst case would occur when K = 1. Hence, the big O time complexity would simply just be O(E log V).

I do not know if my thoughts are correct or if they are, what's the justification for it are.

Math.anony
  • 87
  • 1
  • 6
  • Does this answer your question? [Time Complexity of the Kruskal Algorithm?](https://stackoverflow.com/questions/20432801/time-complexity-of-the-kruskal-algorithm) – Alex K Oct 21 '21 at 16:55

1 Answers1

1

Yes, intuitively you’re saving the cost of comparing edges in one component with edges in another. Formally, f(V, E) ↦ E log V is a convex function, so f(V1, E1) + f(V2, E2) ≤ f(V1 + V2, E1 + E2), which implies that the cost of handling multiple components separately is never more than handling them together. Of course, as you observe, there may be only one component, in which case there are no savings to be had.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120