Slot-size bound for chaining

Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O(lg n/ lg lg n) upper bound on E [M], the expected value of M.

a. Argue that the probability Q_kthat exactly k keys hash to a particular slot is

given by

b. Let P_kbe the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that P_k≤ nQ_k.

c. Use Stirling’s approximation, equation (3.18), to show that Q_k< e^k/k^k.

Equation 3.18

d. Show that there exists a constant c > 1 such that Q_k0< 1/n³for k₀= c lg n/ lg lg n. Conclude that P_k< 1/n²for k ≥k₀= c lg n/ lg lg n.

e. Argue that

Conclude that E [M] = O(lg n/ lg lg n).