Why is the lower bound $m \log n$ for this make-set, union and find-set sequence? 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?
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 .