a. Assuming uniform hashing, show that for i = 1,2, . . . ,n, the probability is
Question:
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/n2) that the i th insertion requires more than 2 lg n probes.
Let the random variable Xi denote the number of probes required by the i th insertion. You have shown in part (b) that Pr {Xi > 2lg n} = O(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} = O(1/n).
d. Show that the expected length E [X] of the longest probe sequence is O(lg n).
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest