0 votes 0 votes 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 Algorithms data-structures kruskals-algorithm time-complexity + – rahul sharma 5 asked Dec 15, 2016 • retagged Jun 30, 2022 by makhdoom ghaya rahul sharma 5 817 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option A is correct Rackson answered Apr 17, 2017 Rackson comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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 Prashank answered Jul 3, 2018 Prashank comment Share Follow See all 0 reply Please log in or register to add a comment.