Disjoint set running time

Hi, does anyone know how to do the question of below :

suppose the disjoint set using both the path compression in Find(x) operation and the weight balance in Union(A,B). There are m operations in Disjoint set and all Union operation appear before the Find operation. How to prove such m operations' total running time is O(m).

thanks in advance

only using path-compression or both path compression and union by rank?

yeah, we would prove if using both path compression and union by rank the running time is O(m). how to prove it ?

Anyway, if only using path-compression, i wonder the running time is O(mlogn) from Tarjan's paper -- worst case of running time for set union (not completely the circumstance with this question). u agree ?

I think you need try to get some cases:

1) base case: [when m = 4]
Call MAKE() 2 times, then UNION() follow by FINDMIN(), that will give u O(1)

and so, do some more case and see do you get O(m), after m operations have been done

Right. Your idea is my first attempt to solve the question, and it could solve the question. But furtherly thinking about, what is the accurate tight-bound (e.g 2n-1 ,where n is the number of the nodes in the D.Set) we would use induction to prove ?
I still thinking about.

So i also try other simple ways to observe the question instead of proof. We are close the answer now ... fun ...