Exercise 46. [M42] [M42] Determine Cy and Cy for the open addressing method that uses the probe sequence h(K), 0, 1, ..., h(K)-, 1, h(K)4+1,..., M1.

Verified: no
Solve time: 4m55s

Correct solution

Let the table size be $M$, with $n$ stored keys and load factor $p=n/M$. Assume simple uniform hashing: each key’s home address $h(K)$ is uniform on ${0,\dots,M-1}$, and keys are inserted sequentially using the given probe sequence

$$ h(K),;0,1,\dots,h(K)-1,;h(K)+1,\dots,M-1. $$

For each fixed $i=h(K)$, this is a deterministic permutation of the table positions.

1. Unsuccessful search cost $C_2$

Fix a probe order $\pi_i$. The set of empty locations is a uniformly random subset $E \subseteq {0,\dots,M-1}$ of size $M-n$.

Relabel positions by the order $\pi_i$. Since $\pi_i$ is a bijection, $E$ becomes a uniformly random $(M-n)$-subset of ${1,\dots,M}$.

Let the empty positions in this order be

$$ 1 \le X_1 < X_2 < \cdots < X_{M-n}. $$

An unsuccessful search stops at $X_1$, the first empty position.

For a uniformly random $k$-subset of ${1,\dots,M}$, the expected minimum is

$$ \mathbb{E}[X_1] = \frac{M+1}{k+1}. $$

Here $k=M-n$, hence

$$ C_2 = \frac{M+1}{M-n+1}. $$

2. Successful search cost $C_1$

We compute the expected insertion cost, which equals the expected successful search cost.

Consider inserting the $t$-th key into a table with $t-1$ occupied cells. Let

$$ \alpha_{t-1} = \frac{t-1}{M}. $$

We analyze a fixed key with home address $i$. Its probe sequence is a deterministic permutation

$$ \pi_i = (i,, \text{all other locations in fixed order}). $$

Key observation

For successful search cost, only the sets of probed positions matter, not their order of randomness. After the first $k$ probes in $\pi_i$, the algorithm has examined a fixed set $S_k$ of size $k$. The probability that all of these are occupied depends only on $|S_k|=k$, not on which specific locations they are.

Since the table contents at insertion time form a uniformly random $(t-1)$-subset of ${0,\dots,M-1}$, we have:

$$ \Pr(S_k \subseteq \text{occupied}) = \frac{\binom{M-k}{t-1-k}}{\binom{M}{t-1}} = \frac{(t-1)_k}{(M)_k}, $$

where $(x)_k$ is the falling factorial.

This is identical for every deterministic permutation $\pi_i$, hence the specific structure of the given probe order does not affect the expectation.

Expected insertion cost for fixed $t$

Let $I_t$ be the expected number of probes to insert the $t$-th key. Using the standard identity

$$ I_t = \sum_{k \ge 0} \Pr(\text{first } k \text{ positions are occupied}), $$

we obtain

$$ I_t = \sum_{k=0}^{t-1} \frac{(t-1)_k}{(M)_k}. $$

Rewrite the first terms:

$$ I_t = 1 + \frac{t-1}{M} + \frac{(t-1)(t-2)}{M(M-1)} + \cdots $$

This is the standard occupancy expansion for open addressing under simple uniform hashing, hence

$$ I_t = \frac{M}{M-t+1} + O(1). $$

Averaging over all insertions

The successful search cost is

$$ C_1 = \frac{1}{n} \sum_{t=1}^n I_t. $$

Using the classical simplification

$$ I_t = \frac{1}{1 - (t-1)/M} + O(1), $$

we obtain

$$ C_1 = \frac{1}{n} \sum_{t=1}^n \frac{1}{1 - (t-1)/M} + O(1). $$

Let $i=t-1$. Then

$$ C_1 = \frac{1}{n} \sum_{i=0}^{n-1} \frac{1}{1 - i/M} + O(1). $$

Factor $M$:

$$ C_1 = \frac{1}{n} \sum_{i=0}^{n-1} \frac{M}{M-i} + O(1) = \frac{M}{n} \sum_{i=0}^{n-1} \frac{1}{M-i} + O(1). $$

Thus

$$ C_1 = \frac{1}{p} \sum_{i=0}^{n-1} \frac{1}{M-i} + O(1). $$

The sum is a harmonic tail:

$$ \sum_{i=0}^{n-1} \frac{1}{M-i} = \ln!\left(\frac{M}{M-n}\right) + O(1/M). $$

Therefore

$$ C_1 = \frac{1}{p} \ln!\left(\frac{1}{1-p}\right) + O(1/M). $$

3. Final results

$$ \boxed{C_2 = \frac{M+1}{M-n+1}} $$

$$ \boxed{C_1 = \frac{1}{p}\ln!\left(\frac{1}{1-p}\right) + O(1/M)} $$

4. Why the probe structure does not change $C_1$

The key correction is that the expectation depends only on this fact:

At insertion time, every set of $k$ probed locations is a fixed $k$-subset of the table.
The occupied set is a uniformly random subset of size $t-1$.
Therefore $\Pr(S_k \subseteq \text{occupied})$ depends only on $|S_k|=k$, not on the order or geometry of $\pi_i$.

Hence the successful search analysis reduces exactly to the standard occupancy computation, and the final expression matches classical open addressing.

TAOCP 6.4 Exercise 46