0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I am just curious, as to why you're not considering the find operation within each union in your analysis? $\endgroup$
    – Russel
    Jun 7, 2022 at 16:44
  • $\begingroup$ 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 $\endgroup$ Jun 7, 2022 at 17:14
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Jun 7, 2022 at 17:16
  • $\begingroup$ @SVMteamsTool where did you get this problem anyway? $\endgroup$
    – Russel
    Jun 8, 2022 at 9:20
  • $\begingroup$ it showed up in a past paper in an algorithms exam in my uni in 2017 (it was framed slightly differently, they only cared about the complexity of the f find operations at the end). On googling the problem I found this - courses.engr.illinois.edu/cs473/sp2010/notes/10-unionfind.pdf . Exercise 3 at the end is the question I asked $\endgroup$ Jun 8, 2022 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.