86 Worst Case for Union-by-Rank and Path Compression (Lemma(Tarjan)) Lett(M, N)be the maximum time required to process an intermixed sequence of finds and N-l unions. Then: k1Ma(M,N)≤T(M,N)≤k2Ma(M,N) for some positive constants K, and k2 G Ackermann's Function and a (M,N) log"2656=5 sInce 2 i=1andj≥1 logloglogloglog (26556)=1 636 A(i,j)={A(i-1,2) i≥2andj=1 A(i-1,A(i,j-1)i≥2andj≥2 http://mathworld.wolfram.com/ackermannfunctIon.html a(M,N)=mini≥1A(LM/N」)>logN}≤O(ogN)≤4 log N(inverse Ackermann function) of times the logarithm is applied to n until the result s 1§6 Worst Case for Union-by-Rank and Path Compression 【Lemma (Tarjan)】Let T( M, N ) be the maximum time required to process an intermixed sequence of M  N finds and N − 1 unions. Then: k1M  ( M, N )  T( M, N )  k2M  ( M, N ) for some positive constants k1 and k2 .        − −   −  = =  = ( 1, ( , 1)) 2 and 2 ( 1, 2) 2 and 1 2 1 and 1 ( , ) A i A i j i j A i i j i j A i j j  (M, N) = min{ i  1| A(i, M N)  log N } Ackermann’s Function and  ( M, N )  O( log* N )  4 http://mathworld.wolfram.com/AckermannFunction.html log* N (inverse Ackermann function) = # of times the logarithm is applied to N until the result  1. A(2,4) = ? 2 65536 2 2 2 2 2 = log* 2 65536 = 5 since logloglogloglog ( 265536 )= 1