# Disjoint Set union complexity when makesets, unions and finds follow a certain order

Consider an arbitrary sequence of $$m$$ MAKESET operations, followed by $$u$$ UNION operations, followed by $$f$$ FIND operations, and let $$n = m + u + f$$ in a disjoint set union data structure. Prove that if we use union by rank and FIND with path compression, all $$n$$ operations are executed in $$O(n)$$ time.

I'm not sure how to prove this bound - the obvious answer is something like $$O(m + \alpha(u+f))$$ but this isn't $$O(n)$$.

The $$m$$ makeset and the $$u$$ union operations are executed in time $$O(m+u)$$, so we only need to argue about the time spent in the find operations. Since this time is proportional to the overall number of traversed nodes, we can focus on this latter quantity instead.
Imagine that all nodes are initially unmarked. An unmarked node $$u$$ becomes marked when a find($$x$$) operation is performed and $$u$$ lies in the unique path between $$x$$ and the root of the tree containing $$x$$. Notice that, as soon as find operation encounters a node $$v$$ that was previously marked, it completes by traversing $$v$$ plus at most $$1$$ additional node. This is because path compression (and the fact that we do not perform any additional merge operation) ensures that $$v$$ is at depth at most $$1$$.
The overall time spent by all find operations is then $$O(f+t)$$, where $$t$$ is the number of times a node becomes marked. Clearly $$t = O(m)$$.
• I'm not entirely convinced by "The m makeset and the u union operations are executed in time $O(m+u)$". We can't apply the same argument as we did for the findsets on their own since a union operation which results in a node ending up at depth 1 might be followed by more union operations which end up making that node's depth deeper Jun 7, 2022 at 17:14
• @Russel. Good point. I forgot to consider that. Interesting the analysis above works if we do not perform any finds in the union($x$,$y$) operations and just add $y$ as a child of $x$ (no union by rank). Then each union requires $O(1)$ time. Jun 7, 2022 at 17:16