Exponential height recurrence E n E>Znk(2. maxrk 1,1n-k k=1 ∑E[zmk(2 maxIk-1>n-l k k=1 22E[Znk ].E[max(Yk-Yn-k3] k=1 Independence of the rank of the root from the ranks of subtree roots c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.20© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.20 Exponential height recurrence [ ] ( ) [ ] ( ) ∑ ∑ ∑ = − − = − − = − − = ⋅ = ⋅   = ⋅ n k nk k n k n k nk k n k n k n nk k n k E Z E Y Y E Z Y Y E Y E Z Y Y 1 1 1 1 1 1 2 [ ] [max{ , }] 2 max{ , } 2 max{ , } Independence of the rank of the root from the ranks of subtree roots