Proof (continued) ECx]=E∑c Take expectation y∈7-{x} of both sides o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.6© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.6 Proof (continued) = ∑∈ −{ } [ ] y T x x xy E C E c • Take expectation of both sides