2
$\begingroup$

Look at this solution:

solution

Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION operations, and then $m - 2n + 1$ FIND-SET operations. The lower bound seems larger to me but what am I missing?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Welcome to the site! So that your question is accessible to search engines and the visually impaired, it would be very helpful if you could transcribe the image to text. Also, you need to give credit to the source of that answer. $\endgroup$
    – David Richerby
    Commented Apr 14, 2017 at 20:13

1 Answer 1

Reset to default
0
$\begingroup$

You are asking two questions.

Is the lower bound only for this specific implementation?

Yes. If you also use path compression, the running time will be $o(m\log n)$.

The lower bound seems to large to me.

Your mistake is that you assume that there are only $\log n$ UNION operations, whereas there are $2^{\lfloor \log_2 n \rfloor}-1 = \Theta(n)$, as the answer clearly .

Improve this answer
$\endgroup$

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.