MIT QUIZ

Question

Answer 1

See 

Initialy table is empty so 1^st element is inserted with Probebility = $\frac{m}{(m)} = 1$

2^nd elemnt witll inserted into two places either just before 1st element and just after first element so choice= $\frac{3}{(m)}$

3^rd element will have only one choce i.e. 1st time coliision then 2nd time collision then get its place using liener fashion = 1/m posiblity.

Total = $\frac{3}{(m)(m)}$

Comments

jeny in pic they take unsuccessfull prob. but the in actual quetion we have to ask the number of suceesfull probs.

The example you gave in this to enter element # unsuceesfull prob and 1 sucessfull prob is needed total 4 . prob means in which place element can insert

---

@Anirudh/@Jeny Could you please explain why in the probablity collision of second key is not taken into consideration?

The first element k1 can occupy any of the 'm' slot. So Prob = (m/m)

The second element k2 can occupy either the slot above the first key (1/m) or below the first key by either hashing to the same slot as k1 or directly below (2/m). So total prob will be (3/m)

In order for k3 to have 3 probes it should hash to the topmost slot ( k1 or k2). So prob = (1/m)

So final prob will be (m/m)(3/m)(1/m)

---

@yash - You are correct.

https://gateoverflow.in/78284/hashing