Open-Addressing Analysis

To discover that k is not in the table, we need to keep probing until we find an empty slot.

Here's a simple (and familiar) upper bound.

$\begin{eqnarraystar} P &=& 1 + \alpha P + (1-\alpha)\cdot 0 \ (1-\alpha)P &=& 1 \ P &=& 1/(1-\alpha)\end{eqnarraystar}$

As an upper bound, we assume that each probe hits a completely random slot. This is an upper bound because the probability that we hit an empty slot goes up as we use up the filled slots.

Next: Punchline Up: ANALYSIS Previous: Chaining Analysis