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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.