cannot find running time of findset in this algorithm

Question

I designed an algorithm and I am trying to find the upperbound and lowerbound for that to be able to conclude theta:

ms(G,w)
for each v in G
      make-set(v)
sort the edges of G.E into non-decreasing order by weight
if(find-set(v) not equal to find-set(u))
     union(u,v)
else
     feed=feed U {edge(u,v)}

as you can see it is very similar to kruskal algorithm. Here my problem is that I can not understand the running time of find-set

for the other part I have:

makeset O(v) sorting O(ElogE) union O(1) but for find set I dont know how to calculate it?(Also can you tell me if calculated running time for union is true)

Answer 1

The big O of of find-set depends on the implementation used.

As an example, take an array of your the data in the set. They are sorted, your can access them them with O(log(N)) (or even O(log(log(N)) but then any insertion is O(N) -- think about you add a new lowest element into our set. You can improve this by using heaps.

Or you store the set in a linked list. Adding and deleting is O(1), but to find it, you'll have to traverse all entries, thus O(N).

You have to decide, which operation is used more often or in a more crucial point of your algorithm.