# 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, ...,

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).

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).

## This problem has been solved!

Do you need an answer to a question different from the above? Ask your question!

**Related Book For**

## Introduction to Algorithms

3rd edition

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

**ISBN:** 978-0262033848