11-2 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 $\text E[M]$, the expected value of $M$.

a. Argue that the probability $Q_k$ that exactly $k$ keys hash to a particular slot is given by

$$Q_k = \bigg(\frac{1}{n} \bigg)^k \bigg(1 - \frac{1}{n} \bigg)^{n - k} \binom{n}{k}.$$

b. Let $P_k$ be the probability that $M = k$, that is, the probability that the slot containing the most keys contains $k$ keys. Show that $P_k \le n Q_k$.

c. Use Stirling's approximation, equation $\text{(3.18)}$, to show that $Q_k < e^k / k^k$.

d. Show that there exists a constant $c > 1$ such that $Q_{k_0} < 1 / n^3$ for $k_0 = c\lg n / \lg\lg n$. Conclude that $P_k < 1 / n^2$ for $k \ge k_0 = c\lg n / \lg\lg n$.

e. Argue that

$$\text E[M] \le \Pr\bigg\{M > \frac{c\lg n}{\lg\lg n}\bigg\} \cdot n + \Pr\bigg\{M \le \frac{c\lg n}{\lg\lg n}\bigg\} \cdot \frac{c\lg n}{\lg\lg n}.$$

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

(Removed)