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-⅄)})

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-⅄)}).