theorem (mnrm log proof we start with lemma (mnrc(mt nt rc(mb nb smt ( )nt ( observe that in the top halfthere are only nodes of rank + + rand thus no node can have its parent change more than ( - - times this yields trivial bound of nt ( - - for (mt nt rthusc(mnrnt ( (mb nb smt ( )nt ( combining termsc(mnrnt ( (mb nb smt ( select / then so (mnrc(mb nb / mt ( equivalentlysince according to lemma mb +mt (the proof falls apart without this) (mnrm (mb nb / mb ( let (mnrc(mnrmthen (mnrd(mb nb / ( which implies (mnrn log this yields (mnrm log theorem any sequence of unions and finds with path compression makes at most log log parent changes during the finds proof the bound is immediate from theorem since <log an om log bound the bound in theorem is pretty goodbut with little workwe can do even better recallthat central idea of the recursive decomposition is choosing to be as small as possible but to do thisthe other terms must also be smalland as gets smallerwe would expect (mt nt rto get larger but the bound for (mt nt rused primitive estimateand theorem itself can now be used to give better estimate for this term since the (mt nt restimate will now be lowerwe will be able to use lower theorem (mnr logr