Lecture MIT WRONG? Analysis of open addressing in hashing
In the next MIT lecture: https://www.youtube.com/watch?v=JZHBa-rLrBA at 1:07:00, the professor taught how to calculate the number of probes in a failed search.
But my calculation method doesn't match it. My answer:
Number of samples = 
m = no. slots in the hash table
n = no. elements (keys)
Explanation:
1. The hash function can fall into an empty slot with probability mn / m.
2.Or it can get into a pre-occupied key slot with probability n / m.
3. Now in case 2 we have to call the hash function again, and there are two possibilities: (i) We get a slot without a key with probability (mn) / (m-1). (ii) We get a slot with a key with probability (n-1) / (m-1).
4. Now repeat register 3, but with different probabilities, as shown in the figure
Why am I getting a different answer. What's wrong with him?
source to share
The task will ask us to find the expected number of probes to be executed in the hash table.
You have to do it no matter what, so you have 1 to start with. Then there is a chance n / m
that you have a collision. You got it right in your explanations.
If you have a collision, you should make another probe (and maybe even more). And so on, so the answer is the one the professor gets:
1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))
You don't multiply with the probability of getting an empty slot. You are multiplying the probability of not getting an empty slot with the number of operations you have to perform unless you get an empty slot (1 because you need to make at least one more probe in this case).
It makes no sense to multiply the probability of getting an open slot with the probability of not getting it, as you do. Remember that we want to find the expected number of probes we need to make. So you are multiplying the number of operations (probes) in each step with the probability that you will not get what you would like to receive (empty slot), because if this event happens then we will need to do more operation (probes) otherwise we're done.
It explains very well in the lecture you linked to if you follow closely to the end.
source to share