Time Complexity of the Kruskal Algorithm?
algorithm, asymptotic-complexity, graph-algorithm, kruskals-algorithm, time-complexity
Solution
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...)
Problem
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.