Dark Mode

6 votes

Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $â€™râ€™$ insertions?

$A)\left ( 1-\frac{N}{k} \right )^{r}$

$B)\left ( 1-\frac{k}{N} \right )^{r}$

$C)\left ( 1+\frac{N}{k} \right )^{r-1}$

$D)\left ( 1-\frac{k}{N} \right )^{r-1}$

$A)\left ( 1-\frac{N}{k} \right )^{r}$

$B)\left ( 1-\frac{k}{N} \right )^{r}$

$C)\left ( 1+\frac{N}{k} \right )^{r-1}$

$D)\left ( 1-\frac{k}{N} \right )^{r-1}$

1 vote

Here, We are using chaining as a resolution technique so if a collision happens at some place then we will get an extra bucket at that place.

Now here in question, we have **N slots** and we don't want any insertion in the **last K slots**, so remaining slots where we can insert value is **N-K slots.**

**First Insertion** :

The probability that the first insertion done at N-K slots is, (N-K/N)

**Second Insertion** :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) = (N-K/N)^2

**Third Insertion** :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) * (N-K/N)= (N-K/N)^3

**so for, rth Insertion** :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) * ...... r times= (N-K/N)^r

**So answer is (N-K/N)^r which is nothing but (1-(K/N))^r Option B**

0 votes

Option b. Since chaining is used

For 1st insertion :(N-k) slots will be used for insertion only as k slot to be left unfilled

Similarly for 2nd and 3rd insertion because here in chaining we can use same slot again and again according to hash function there is not chance of collision so (N-k) slot for 2nd 3rd insertion too

Total no of possibility for r insertion =N^r

Therefore probability =(N-k) ^r/N^r

For 1st insertion :(N-k) slots will be used for insertion only as k slot to be left unfilled

Similarly for 2nd and 3rd insertion because here in chaining we can use same slot again and again according to hash function there is not chance of collision so (N-k) slot for 2nd 3rd insertion too

Total no of possibility for r insertion =N^r

Therefore probability =(N-k) ^r/N^r

0 votes

Let N=6 , k=2 and r =4;

<---------------- k ---------------->

<---------------------------------------------------- N ---------------------------------------------------->

First insertion :

probability that the last k slot unfilled = 4/6;

Second insertion :

probability that the last k slot unfilled = 4/6*4/6; **[ Since collision resolution is done using chaining]**

third insertion:

probability that the last k slot unfilled = 4/6*4/6*4/6;

fourth insertion

probability that the last k slot unfilled = 4/6*4/6*4/6*4/6;

i.e. **probability that the last k slot unfilled after 4th insertion is = (4/6)^4;**

** probability that the last k slot unfilled after rth insertion is = (N-k/N)^r;**

** = (1 - k/N )^r;**

**Option B**