Calculating expectation E[T(n)=E 2Xk(T(max(k,n-k-1)+O(n) k=0 k=o k((max(k, n-k-1)+O(n)7 ∑E[X Linearity of expectation o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.9 Calculating expectation ( ) ∑ [ ] ( ) ∑ − = − = = − − + Θ   = − − + Θ 1 0 1 0 (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k E X T k n k n E T n E X T k n k n Linearity of expectation