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

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)