What is the time complexity of Make-set function in kruskal algorithm ?

Question

what is the time-complexity in kruskal algorithm for the overall step 2 where for each vertex Make-set function is called ? How come overall time for this step  is O(v log v) ? 

We are performing this Operation for all the vertices in the Initial phase only so for every iteration , we have a single set for one vertex so in each iteration we are making one set for one element so how come overall time is O(vlogv) ?
We perform Make-set operation only once right because after we come out of loop we have v sets of 1 vertex each .

Please explain this clearly .

Comments

What i thought is just make one more array With name Leader... And keep its Original value As MAKESET ===> O(1)

 

When you union the edges... Just update the Leader index value. This will help us in findset(u).

---

@Shaik

Can u plz elaborate more?

---

Let there are 5 vertices...
I am taking Leader[5], and by using make set, we initialize this array with one,two,three etc

At step no 8 in algorithm, we update the value[vertex] with minimum of u,v... This property will help us at step no 6

Answer 1

select  all vertices through makeset will take time O(V)

and for checking cycle detection it use path compression algorithm ,it takes O(log V)

so overall complexity is O(V logV)

Comments

for checking cycle detection it use path compression algorithm ,it takes O(log V)

what do you mean?

---

select sorted edges one by one and whenever cycle is formed reject that edges

---

no it is never VLOGV

Answer 2

Refer this

 

http://lcm.csa.iisc.ernet.in/dsa/node184.html

 

with path compression given it takes $O(e  \alpha e)$ time

where $\alpha e$ is the inverse  ackerman function

 

https://sites.google.com/site/gabrielnivasch/fun/inverse-ackermann

 

else without path compression it takes $O(ElogE)$ in the worst case