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 = max≤ ≤ 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).

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: