Exponential height recurrence E=E∑2mk(2maxx-,mk ∑Ez nk(2. maxEy_.. k k=1 =2∑EZm]E[maxx1,nk k=1 2YELK-1 k The max of two nonnegative numbers is at most their sum, and elZnk=l/n c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.21 Exponential height recurrence [ ] ( ) [ ] ( ) ∑ ∑ ∑ ∑ = − − = − − = − − = − − ≤ + = ⋅ = ⋅   = ⋅ n k k n k n k nk k n k n k nk k n k n k n nk k n k E Y Y n E Z E Y Y E Z Y Y E Y E Z Y Y 1 1 1 1 1 1 1 1 [ ] 2 2 [ ] [max{ , }] 2 max{ , } 2 max{ , } The max of two nonnegative numbers is at most their sum, and E[Znk] = 1/n