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)$.
