Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?
-
04-11-2019 - |
Question
Look at this 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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange