Time Complexity of the Kruskal Algorithm?

Question

I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached)

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

The CLRS Algorithm:

Is it correct or I'm doing something wrong please tell.

Answer 1

Kruskal is O(E log E); your derivation is right. You could also say O(E log V) because E <= V * V, so log(E) <= 2 log(V) (I don't know why I remember that, other than that I think a prof put that on an exam at one point...)

Answer 2

O(ElogE) is definitely O(ElogV) because E <= V^2 (fully connected graph)

ElogE <= Elog(V^2) = 2ElogV = O(ElogV)

Answer 3

All other answers are correct, but we can consider the following case, that gives us the time complexity of O(|E|).
The following answer is from Algorithms book by Dasgupta, chapter 5, page 140, section path compression:
In the time complexity computation of this algorithm, the dominant part is the edge sorting section which is O(|E| log|E|) or as all other answers explained O( |E|. log|V|).

But, what if the given edges are sorted?
Or if the weights are small (say, O(|E|)) so that sorting can be done in linear time (like applying counting sort).
In such a case, the data structure part becomes the bottleneck (the Union-find) and it is useful to think about improving its performance beyond log n per operation. The solution is using the path-compression method, while doing the find() operation.

This amortized cost turns out to be just barely more than O(1), down from the earlier O(log n). For more details please check this reference. The brief idea is, whenever the find(v) operation is called to find the root of a set which v belongs to, all the nodes' links to their parent will be changed and will point out to the root. This way if you call find(x) operation on each node x on the same path, you will get the set's root (label) in O(1). Hence, in this case, the algorithm bottleneck is the Union-find operation and using the described solution it is O(1), the running time of this algorithm in the described situation is O(|E|).

Answer 4

Sorry for the late reply.
Runtime for Kruskal algorithm is O(E log E) and not O(E log V).

As, the edges have to be sorted first and it takes O(E log E) where it dominates the runtime for verifying whether the edge in consideration is a safe edge or not which would take O( E log V). And |E| > |V|((corner case if the graph is already a tree)), so its safe to assume the runtime is O(E log E)

Answer 5

Since |V| > |E|+1, we prefer a tight upper bound with V terms instead of E terms.

    |E| <= |V|²   
.   log |E| < log |V|²   
.   log |E| < 2 log |V| 
.   running time of MST-KRUSKAL is: O(E log V)

Answer 6

line 5 to 9 the complexity is O(E).

5. O(E)
6. O(1)
7. O(1)
8. O(1)
9. O(1)

till the line 5 you have calculated the complexity rightly. Finally, the Dominating factor here is O(E lg E). So, the complexity is O(E lg E)