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

The question is a bit ambiguous.

After hashing of how many keys, will the probability that any new key hashed collides with an existing one exceed 0.5.

Here, 'new key hashed' is the ambiguity. It can mean the probability of a collision in the next 'hash', or the probability of a collision in any of the hashes of the 'new keys' starting from the first insertion. For the first case answer must be $10$ to get probability equal to $0.5$, and so $11$ must be the answer for probability $> 0.5$. Thus we can conclude from given choices, it is the second case. 

So, we need to find $n$ such that after $n$ hashes, probability of collision (in any of the $n$ hashes)  $> 0.5$. 

Probability that there will be a collision after $n$ hashes (a collision happened in at least one of those $n$ hashes) $= 1 - $Probability that there was no collision in the first $n$ hashes

$= 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$. 

So, we need,

$0.5 < 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$. 

$\implies \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20} < 0.5$.

For $n=5$, we get, $0.5814$ and for $n=6$, we get $0.43605$. So, answer should be $n = 6$.

Correct Answer: $B$

Comments

After hashing of 10 keys, there are 10 slots that are filled. So the probability that the new key collides will be 10/20 = 0.5 and not 11/20

---

@BeBetter it will be 10/20 only

---

Someday Amitabh bachchan would ask ARJUN sir “Kya kijiyega itni knowledge ka”😂😂

Answer 2

He has asked "after how many insertion" or in which insertion probability will be >= 0.5

So after 10 keys has been inserted probability of collision will be 0.5

We can simply think like this :there are 20 slots out of which 10 are full. So there is half probability of collision. if there were less than 10 values prob. of collision would never exceed 1/2 rather it would decrease.

So answer less than 10 is not possible at all

Correct answer is (D) only.

Also probability in 'k' th insertion is  (k-1)/20

(k-1)/20 >=0.5

which gives k>=11

means in 11 th insertion we get required prob .  OR after inserting 10 values prob will exceed 0.5

Comments

This is the most logical and beautiful solution of this question.

---

It is important to note that 

Also probability in k ^th insertion is  (k-1)/20 

It means the probability of collision at k^th insertion ,it is not the probability of first collision at k^th insertion like in this question  https://gateoverflow.in/2272/gate1997-12 c part   :)

---

waoo what a beautiful sol u given with best logic

Answer 3

Ans: D (10)

Comments

I think answer is (D).

• These three links are supporting your answer and are logical too.

https://math.stackexchange.com/questions/2870603/after-hashing-of-how-many-keys-will-the-probability-that-any-new-key-hashed-coll

https://www.geeksforgeeks.org/gate-gate-it-2007-question-28/

https://prepinsta.com/questions-hash-tables-sapient-razorfish/

 

• But below given link is supporting answer selected as best answer and giving the same explanation as above.

https://gatecse.in/w/images/4/4c/Hashng.pdf

 

---

Isn't this same as "The probability of collision on the (i+1)th insertion exceeding 0.5?

https://gateoverflow.in/2272/gate1997-12

Part C. Here we considered the probabilities of no collisions till i insertions in the solution. Why didn't we consider it here?

---

@Kuljeet Shan 

The probability of collision for 11th insertion (after 10 hashing) will be exactly 10/20 =0.5

After 11 hashing (for 12th) prob. of collision>0.5

 

Answer 4

After the 10th insertion, probability of collision of new key hashed= 10/20= 0.5

After 11th insertion, probability of collision of new key hashed= 11/20 > 0.5

We are asked after which insertion, probability of collision of new key hashed exceeds 0.5. So it should be 11.

Comments

nice concept