Exponential height recurrence E[Yn]-E2Zn(2. max(Yk-1,n-k, k=1 ∑E[zmk(2 maxlk-1,In-k k=1 Linearity of expectation c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.19© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.19 Exponential height recurrence [ ] ( ) ∑ [ ] ( ) ∑ = − − = − − = ⋅   = ⋅ n k nk k n k n k n nk k n k E Z Y Y E Y E Z Y Y 1 1 1 1 2 max{ , } 2 max{ , } Linearity of expectation