Sir doubt in kruskal algorithm

#1

Sir what is the timecomplexity of kruskal algorithm as we have that we implemented O(NLogn+N)?? due to sorting??

#2

hello @tejasddongare
let E be the edge , V be the verticies.

sorting time will be -> ELog(E)
now we need to pick E-1 edges with no cycle , for checking cycle we are using union find datastruture which take Log(v) per operation.
so time used in this will be E log(V)

so total time will -> Elog(E) + E log(V) -> E( log(e) + log(v) )

and becuase v > e we ignore log(e)
so
time complexity will be
E(log(v))

#3

sir what but findset function will take O(1) on average time so how are we taking O(logV)???

#4

refer this->
wiki

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.