Q12

MCQMarks unknown

Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$ . The hash table is initially empty and $K$ distinct values are inserted in the table.

(A)

What is the probability that bucket number $1$ is empty after the $K^{th}$ insertion?

(B)

What is the probability that no collision has occurred in any of the $K$ insertions?

(C)

What is the probability that the first collision occurs at the $K^{th}$ insertion?

Loading…