8 views

https://gateoverflow.in/57653/cormen-2nd-edition-exercise-11-2-1

WHY WE CANT DO LIKE THIS …...NUMBER OF COLLISIONS(X) : 0        1        2          3       4    …………………...N-1

P(X):   0/M   1/M    2/M…………………… … ………….(N-1)/M

ago in DS | 8 views
0

WHY WE CANT DO LIKE THIS

You can, but to get the expected value you would have to multiply them and sum them up.

0
ya i am multiplying them and doing their sum  but see the approach it is different …..they are multiplying by 1 every time ...
0

Ok, I think I know what’s wrong here, the value of probability you are calculating is the probability of collision at nth insertion, not the probability of exactly k collisions.

0
ya exactly ...but how will it happen if i do like i am thinking ? and why 1 is multiplied every time in the solution?
0

how will it happen if i do like i am thinking

Then you would have to calculate the probability of exact k collision and multiply it with k, and what I’ve looked online this is not easy.

0
ok it is  difficult…..so can u please explain what is the meaning of multiplying by 1 in each term? not able to relate with concept of expectation ...
0

Maybe it’s because the number of new collision that may have occurred at kth collision is 1, and the probability of collision at kth insertion is k-1/m.

So expected value of new collision = $1 \times \frac{k-1}{m}$

We want the expected value of collisions when n values are hashed into the table, so we can just sum them up $$\sum_{k=1}^{n}\frac{k-1}{m}$$ to get the expected number of collisions as expected value of the sum of several random variables is equal to the sum of their expectations.

0
ok thank u for efforts…..