- #1

- 143

- 1

## Homework Statement

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 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}## insertions ?

## Homework Equations

## The Attempt at a Solution

Probability that a key value is hashed to the first bucket = ##\frac{1}{n}##

Probability that a key value is doesn't hashed to the first bucket = ##1 - \frac{1}{n}## = ##\frac{n-1}{n}##

(a) Probability that bucket number 1 is empty after the the ##K^{th}## insertion = ##(\frac{n-1}{n})^k##

(b) Probability that no collision has occurred in any of the ##K## insertions = ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-1)}##

(c) Probability that the first collision occurs at the ##K^{th}## insertions = ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)} \times \frac{1}{k-1}##

are my above ans correct or I've done some mistake. Please share