A hash table has space for $75$ records, then the probability of collision before the table is $6\%$ full
- $0.25$
- $0.20$
- $0.35$
- $0.30$
$\color{Green}{\text{My attempt:}}$
Table has $75$ slots. So, for $6\%$ filling it must take $6$ slots. Now, the question is like this- collision before $6\%$ full. This should mean the first collision happened before the $6th$ entry is made. So, the first collision can happen from $2nd$ entry (for $1st$ entry there won't be a collision) to $6th$ entry. So required probability
$=\cfrac{75\times 1}{75^2}+\cfrac{75\times74\times 2}{75^3}+\cfrac{75\times74\times73\times 3}{75^4}+\cfrac{75\times74\times73\times 72\times4}{75^5}+\cfrac{75\times74\times73\times 72\times71\times5}{75^6}=0.1854$
$\color{Red}{\text{Somewhere it explained as:}}$
To make the table $6\%$ full, we need to insert at least $\lceil{\cfrac{75\times 6}{100}}\rceil = 5$ values.
probability of collision during first insertion $= 0$
probability of collision during second insertion $= 1/75$
probability of collision during third insertion $= 2/75$
probability of collision during fourth insertion $= 3/75$
probability of collision during fifth insertion $= 4/75$
So, total probability of collision to make the table $6\%$ full $= (1+2+3+4)/75 = 0.13$
$\color{blue}{\text{Another explanation is given as :}}$
Explanation:
On $.75^{th}$ insertion probability of collision $= 1/75$
On $1.5^{th}$ insertion probability of collision $= 2/75$
On $2.25^{th}$ insertion probability of collision $= 3/75$
On $3^{th}$ insertion probability of collision $= 4/75$
On $3.75^{th}$ insertion probability of collision $= 5/75$
So the required probability is $1+2+3+4+5/75 = 0.20$
Can you explain it, please?
Best Answer
First explanation is correct. Alternative solution is:
Table has $75$ slots. So, for $6\%$ filling it must take $6$ slots. Probability of no collision for first $6$ entries $ = \cfrac{^{75}P_6}{ 75^6} = 0.814586387 $
Therefore, at least one collision occurs in $6$ entries
$= 1 - \text{Probability of no collision for first $6$ entries }$
$= 1 - 0.814586387$
$= 0.185413613$