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
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