retagged by
1,323 views

3 Answers

5 votes
5 votes
The hash table requires probability for the 10% of 100 records which is only 10 slots.

The complement approach will be better for this one.

Probability / of no collision at the first entry =100/100=1

Probability of no collision at the second entry =99/100

Probability of no collision at the third entry =98/100
.
.
.

Probability  of no collision at the tenth entry =91/100

Now all these probability are independent events as the collision in the first collision has nothing to do with the next time

So probability of no collision for the first ten insertions=100.99.98....91/(100)¹⁰ =0.628

 

∴Required probability=1-0.628=0.372

 

Hence option d is the correct answer
edited by
1 votes
1 votes
For the first time there will be no collision because all the slot is empty.
Now, once the first slot is filled, after then to fill the next key in the slot there is chances of collision by 1/100.
For the next key, 2/100.
So 1/100 + 2/100+.............+9/100.
= .01+.02+.03+.......+.08+.09= .45
0 votes
0 votes

Option D

Probability of no Collision for first 10 entries is
= 100.99.98.97.96.95.94.93.92.91/100^10 = 0.628
So, probability of collision before the table is 10% full is
= 1 – Probability of no Collision for first 10 entries
= 1 – 0.628 = 0.37(approx.)

Answer:

Related questions

0 votes
0 votes
2 answers
1
admin asked Mar 31, 2020
1,282 views
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored...
4 votes
4 votes
11 answers
2
admin asked Mar 31, 2020
15,478 views
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$?Insertion sort.Merge sort.Quick sort.Bubble sort.
1 votes
1 votes
2 answers
3
admin asked Mar 31, 2020
1,401 views
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by$\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \en...
8 votes
8 votes
10 answers
4
admin asked Mar 31, 2020
2,292 views
Which of the following logic expression is incorrect?$1\oplus0=1$$1\oplus1\oplus0=1$$1\oplus1\oplus1=1$$1\oplus1=0$