What is the expected number of probes in a successful search

Question

consider an open address hash table with a total of 10000 slots containing 9800 entries.
a) 2
b) 3
c) 4
d) 4.5

Answer 1

Given, Open address hash table

No of slots (m) = 10000

No of Keys (n) = 9800

Then

Load factor ($\alpha$) = ($\frac{n}{m}$) = ($\frac{9800}{10000}$) = $0.98$

and There is a theorem in CLRS, (you can check that.) which states that, expected number of probes in a successful search is at most ($\frac{1}{\alpha} ln \frac{1}{1-\alpha}$)

Hence answer will be =  ($\frac{1}{0.98} ln \frac{1}{1-0.98}$)

                                = 3.991860..

                                = 4

Hence Answer will be (C). 4

Comments

Answer is right but not understand, can you clear more?

---

Thanks bro