a. Assuming uniform hashing, show that for i = 1,2, . . . ,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, . . . ,n, the probability is O(1/n²) 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 > 2lg n} = O(1/n²). Let the random variable X = max_{1 ≤ i ≤ n} X_i denote the maximum number of probes required by any of the n insertions.

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

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