1
$\begingroup$

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.

$\endgroup$

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.