In Union-Find with link-by-rank but no path compression find a sequence of operations Make-Set, Find, Union of length $m$, containing $n$ Make-Set operations, and with time complexity in $\Omega(m\log n)$.

My idea was to spawn $n$ nodes with $n$ Make-Set operations and then create a "tree" with $\log n$ height out of them. That would take $\frac{n}2 + \frac{n}4 + \ldots + 1$ (this sequence is $\log n$ long) Union operations.

Now I would be able to keep calling Find on this tree as long as necessary.

However I have no idea if this is the right way because I don't know how to sum up the complexity of the sequence of these operations.



Your Answer

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