GATE IT 2007 | Question: 28

Question

Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$.

• A. $5$
• B. $6$
• C. $7$
• D. $10$

Comments

Thanks for the video.

---

Which is the correct answer here D or B?

Personally I am getting ‘D’ as the answer.

---

After hashing of $\text{how many keys}$ will the probability that any new key hashed collides with an existing one exceed $0.5$.

If we insert a new key then it will collide with existing one and probability of collision $> 0.5$

 $\therefore \text{Probability of collision > 0.5}$

$1 – \text{P(No collision)>0.5}$

Let’s see if we insert $5$ keys then what happens:

$1-(1\times (\frac{20-1}{20})\times (\frac{20-2}{20})\times (\frac{20-3}{20})\times (\frac{20-4}{20}))$
$1-(1\times \frac{19}{20}\times \frac{18}{20}\times \frac{17}{20}\times \frac{16}{20})$
$1-0.5814 = 0.4186$

$\color{Red}0.4186<0.5$

Now we see if $6^{th}$ key inserted what will happen:

$1-(1\times (\frac{20-1}{20})\times (\frac{20-2}{20})\times (\frac{20-3}{20})\times (\frac{20-4}{20})\times (\frac{20-5}{20}))$
$1-(1\times \frac{19}{20}\times \frac{18}{20}\times \frac{17}{20}\times \frac{16}{20}\times \frac{15}{20})$
$1-0.43605 = 0.56395$

$\color{Green}0.56395>0.5$

But the question which is asked a bit ambiguous statement.
My thought:
After hashing of “how many keys” will the probability that any new key hashed collides with an existing one exceed $0.5$.

After hashing of $5$ keys probability that any new key $(6^{th})$ hashed collides with an existing one exceed $0.5$.

Means After hashing of $5$ keys if we hash a new key $(6^{th})$ which collides with an existing one then the probability of collision will exceed $0.5$. which is TRUE.

According to me the ans should be: $A. 5$

$D. 10$ can’t possible as there probability will be equal to $0.5$. Here, $11$ should be ans where probability exceed $0.5$.

Answer 1

tell me if this approach is right or wrong
chances of collision of first element =0
chances of collision of 2nd element is 1/20

chances of collision of 3rd element is 2/20
.
.
.
.
and so on
we have to insert elements till our probability doesnt exceed 0.5 and the moment it exceeds 0.5 we take that nth number as our answer
probability = 0+1/20+2/20+3/20+4/20+...... so on till our value doesnt exceed 0.5
we can see for 5 elements our probability becomes => (0+1/20+2/20+3/20+4/20) which is equal to 0.5
now when we include 6 th element our probabilty will become 0.5+5/20 which is greater than 0.5 so 6 should be answer

Answer 2

Very Simple Question:

When first key is inserted : probability of collision: 0

When Second key is inserted : probability of collision: 1/20 , because there is only one place at which collision is possible out of 20 places

When Third key is inserted : probability of collision: 2/20... and so on.

Answer is :10

Answer 3

it is asking about exceed 0.5 which is 11 because it is not given in the option then we can mark 10 (thats all).

Answer 4

Let P = Probability that newly hashed key collides with an existing one. Given P>0.5.

Let (1-P) be the probability that newly hashed key does not collide with existing one. Thus (1-P)<=0.5

Let “i” keys be already present in table. Thus number of free slots are (20-i) .

Thus (20-i)/20 <=0.5

Thus i>=10