Proof of theorem Proof. Let Cr be the random variable denoting the total number of collisions of keys in Twith x and let 1 if h(x)=h(v) 0 otherwise Note:Ecn]=1 /m and c=∑ Xy y∈7-{x} o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.5 Proof of theorem Proof. Let Cx be the random variable denoting the total number of collisions of keys in T with x, and let cxy = 1 if h(x) = h(y), 0 otherwise. Note: E[cxy] = 1/m and ∑ ∈ − = y T {x} x xy C c