Calculating expectation E[T(m)=E∑x(7(max伙k,n=k-1)+(m) k=0 XELXk(T(max(k, n-k-1))+O(n) k=0 ZELXK.E[T(max k, n-k-1))+O(n) Independence of X, from other random choices o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.10© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.10 Calculating expectation ( ) [ ] ( ) ∑ [ ][ ] ∑ ∑ − = − = − = = ⋅ − − + Θ = − − + Θ   = − − + Θ 1 0 1 0 1 0 (max{ , 1}) ( ) (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k n k k E X E T k n k n E X T k n k n E T n E X T k n k n Independence of Xk from other random choices