the disjoint sets class for the number of parent changes by splitting the charges into the top and bottom groups one of the key ideas is that recursive formula is written not only in terms of and nwhich would be obviousbut also in terms of the maximum rank in the group lemma let (mnrbe the number of parent changes for sequence of finds with path compression on items whose maximum rank is suppose we partition so that all nodes with rank at or lower are in the bottomand the remaining nodes are in the top assuming appropriate initial conditionsc(mnrc(mt nt rc(mb nb smt nnrb proof the path compression that is performed in each of the three cases is covered by (mt nt rc(mb nb snode in case is accounted for by mt finallyall the other bottom nodes on the path are non-root nodes that can have their parent set to themselves at most once in the entire sequence of compressions they are accounted for by nnrb if union-by-rank is usedthen by lemma every top node has children of ranks prior to the commencement of the partial find operations each of those children are definitely root nodes in the bottom (their parent is top nodeso for each top nodes nodes (the children plus the top node itself are definitely not included in nnrb thuswe can refomulate lemma as followslemma let (mnrbe the number of parent changes for sequence of finds with path compression on items whose maximum rank is suppose we partition so that all nodes with rank at or lower are in the bottomand the remaining nodes are in the top assuming appropriate initial conditionsc(mnrc(mt nt rc(mb nb smt ( )nt proof substitute nnrb ( )nt into lemma if we look at lemma we see that (mnris recursively defined in terms of two smaller instances our basic goal at this point is to remove one of these instances by providing bound for it what we would like to do is to remove (mt nt rwhybecauseif we do sowhat is left is (mb nb sin that casewe have recursive formula in which is reduced to if is small enoughwe can make use of variation of equation ( )namelythat the solution to <= ( ( tf(nm > is ( ( )solet' start with simple bound for (mnr)