in DS
230 views
0 votes
0 votes

 

I am getting answer as 0.6 

My approach if in the next two insertions we require atleast one collision , so if in 2 insertions , we have just one collision then it is 30/50*20/50  , if we have 2 collisions in the next 2 insertions , we get 30/50*30/50 , adding them gives 0.6 .

What's wrong in this method ?

in DS
230 views

2 Answers

1 vote
1 vote
Best answer

Answer: 0.848

Explanation:

Way1:

Given,

Table size: 50

Already filled with 30 elements.

Probability that at least one collison occurs:

Element 1 Element 2
Collison No Collison
No Collision Collision
Collision Collision

Case 1: Element 1 collides and element 2 does not

(30/50) *(50-31)/50.........................(A)

Since first element collided and now fills another row, the empty rows reduce by 1

Case 2: Element 1 does not collide and element 2 does

Since first element does not collide there 20 rows which are empty, after first element is inserted another row is used and  the number of rows at which collision could occur increases from 30 to 31.

(20/50) * (31/50)..................(B)

Case 3: Both the elements collide

30 rows where first element could collide. After collision first element is placed at appropriate location and the number of rows in which collision could occur increases by 1.

(30/50) * (31/50).........................(C)

 

Adding up all the cases

2120/2500=0.848

 

Way 2:

1- probability(no collisions occur)

Since first insertion doesn't lead to any collision 20/50. The first element takes another row hence 19 empty rows 19/50.

1- [(20/50)*(19/50)]

1-0.152=0.848

selected by
1 vote
1 vote
C=probability of collision=3/5 N=probability of Not collision =2/5

Probability of at least one collision=CN+NC+CC

=3/5*2/5+2/5*3/5+3/5*3/5=21/25=0.84

Related questions

1 vote
1 vote
2 answers
1