168 views
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}$
in DS | 168 views

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
by (145 points)
edited by
0
for 1st insertion N-1 slot left unfilled

right?

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

by (11 points)
0
Can it be thought like that the probability of filling k slots out of N is k/n right now probability of not filling those k slots would be 1- k/n right now we want only r insertions not more than that so it would be raised to the power r please have a look at this logic is it right

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

by (483 points)