reopened by
1,066 views
0 votes
0 votes
A hash table has space for 100 records .what is the probability of collision before it is 5% full??

 

a. 0.25

b. 0.10

c. 0.40

d. 0.20
reopened by

3 Answers

2 votes
2 votes

 required probability =   ((100*1 )/ 1002) + ((100*99*2 ) / 1003) +.....+((100*99*98*97*4 ) / 1005) = 0.096= 0.10( appox)

option B is correct

edited by
2 votes
2 votes
5 % of 100 is 5. So we have to insert 5 elements for making the hash table 5% full.

Probability of collision during first insertion = 0

Probability of collision during second insertion = 1/100 (Collision occurs only if trying to insert in previously inserted location)

Probability of collision during third insertion = 2/100

Probability of collision during fourth insertion = 3/100

Here, it is asked to consider probability before 5% full. So we consider only 4 insertions. We need not consider fifth insertion, as it will make the table 5% full.

Therefore, total probabilty of collsion = 0 + (1/100) + (2/100) + (3/100) = 0.06 $\approx$ 0.1
0 votes
0 votes

Hash table will be 5% full.

Max collision possible,

In 1 insertion of record there is 0 collision.

" 2      "       "     "         "     "  1    "

"  3     "       "     "         "     "   2   "

"  4    "        "     "        "     "  3   "

Before 5% full there are maximum 6 collision

So, there are total collision possible 0+1+2+.....+6=21