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

+1 vote
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.

## 1 Answer

0 votes
by (672k points)
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-⅄)}$.

+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+2 votes
1 answer