in DS
4,223 views
6 votes
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}$
in DS
by
4.2k views

4 Answers

1 vote
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

1 comment

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
0
0
0 votes
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
edited by

2 Comments

for 1st insertion N-1 slot left unfilled

right?
0
0
No. Question says collision resolution by chaining. So to same slot it maybe mapped and will be stored using chaining during collision.
0
0
0 votes
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

 

0 votes
0 votes
There are n slots,After r insertion k slots are unfilled ,

for first insertion , i have (n-k)/n options

for second insertion,i have (n-k)/n options because we use chaining for collision resolution

same as for 3,4,5 upto r insertions

so that ((n-k)/n)^r

Ans  B

Related questions