Question

What is the formula to find the expected number of probes for an unsuccessful search in linear probing?

(a) \(\frac{1}{2} \frac{1+1}{(1-⅄)}\)

(b) \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\)

(c) \(\frac{1}{2}\frac{1+1}{(1+⅄)}\)

(d) \(\frac{1}{2}\frac{1+1}{(1+⅄)(1-⅄)}\)

My question is based upon Hash Tables in section Hash Tables of Data Structures & Algorithms I

I got this question during an online interview.

Answer 1

The correct option is (b) \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\)

The best I can explain: The mathematical formula for calculating the number of probes for an unsuccessful search is \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\). For insertion, it is \(\frac{1}{2} \frac{1+1}{(1-⅄)}\).