# Proof of expected number of probes in an unsuccessful search (open addressing hashing)

I'm seeking some clarification on the proof of the expected number of probes in an unsuccessful search in open addressing hashing. The proof is given in CLRS on page 275, section 11.4 (Open addressing).

Specifically, why is the higher bound of an expectation (of unsuccessful probes) in search is $\infty$? What is the rational behind this?

$E[X] = \sum_{i=1}^{\infty} Pr\{X \geq i \}$ $(1)$ p. 275 CLRS

My understanding is that the maximum possible amount of probes in the worst case scenario is $n$. So, the expectation in this case is

$E[X] = \sum_{i=1}^{n} Pr\{X \geq i \}$ $(2)$

where n is the number of elements in a table of size m.

Of course, we can assume that $n \rightarrow \infty$, then $(1)$ makes sense. However, open addressing hashing is not recommended for large data sets. So, these two concepts contradict each other.

• So what is recommended for large data sets? Jun 15, 2018 at 22:56
• Chaining can be an effective solution for large data sets Jun 16, 2018 at 23:33