Analysis(continued) Define the indicator random variable znk as I if the root has rank k k 0 otherwise Thus, Pr(Znk=)=elnk=I/n,and Yn-2Znk(2. max( Yk-1,)) k=1 c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.17© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.17 Analysis (continued) Define the indicator random variable Znk as Znk = 1 if the root has rank k, 0 otherwise. Thus, Pr{Znk = 1} = E[Znk] = 1/n, and ∑ ( ) = − − = ⋅ n k Yn Znk Yk Yn k 1 1 2 max{ , }