A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution.
a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.
b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.
c. Show that Pr{X > 2lg n} ≤ 1/n.
d. Show that the expected length E[X] of the longest probe sequence is O (lg n).