Kruskals MST

Question

Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?

a.) E+ElogV

b.)VlogV

c.)V^2

d.)Vlog^2V

Answer 1

option A is correct 

Answer 2

Option A is correct using path compression and union by rank in disjoint set data struture implementation using array data struture a combination of M uninon and find operation will take O(N+Mlog*N) where log* is very slowly growing function. In physical large  values of  value of log* is 5.Please read about Ackermann function. In kruskal algorithm N=V and M=O(E) so combination of find and union operation will take O(V+Elog*V) for dense graph its equal to O(E).

And time for sorting the edges will O(ElogV). so total time will be E+Elogv