11-1 Longest-probe bound for hashing

Suppose that we use an open-addressed hash table of size $m$ to store $n \le m / 2$ items.

a. Assuming uniform hashing, show that for $i = 1, 2, \ldots, n$, the probability is at most $2^{-k}$ that the $i$th insertion requires strictly more than $k$ probes.

b. Show that for $i = 1, 2, \ldots, n$, the probability is $O(1 / n^2)$ that the $i$th insertion requires more than $2\lg n$ probes.

Let the random variable $X_i$ denote the number of probes required by the $i$th insertion. You have shown in part (b) that $\Pr\{X_i > 2\lg n\} = O(1 / n^2)$. Let the random variable $X = \max_{1 \le i \le n} X_i$ denote the maximum number of probes required by any of the $n$ insertions.

c. Show that $\Pr\{X > 2\lg n\} = O(1 / n)$.

d. Show that the expected length $\text E[X]$ of the longest probe sequence is $O(\lg n)$.

(Removed)