Proof (continued) ECx=E|∑cy·. Take expectation y∈7-{x} of both sides E Xy ]· Linearity of y∈7-{x} expectation o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.7© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.7 Proof (continued) ∑ ∑ ∈ − ∈ − =   = { } { } [ ] [ ] y T x xy y T x x xy E c E C E c • Linearity of expectation. • Take expectation of both sides