Exponential height recurrence E[Yn]=E ZZn(2. max(Yk-I, n-k) k=1 Take expectation of both sides c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.18© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.18 Exponential height recurrence [ ] ( )  = ∑ ⋅ = − − nk E Yn E Znk Yk Yn k 1 1 2 max{ , } Take expectation of both sides