GATE 2024 DA Q.21: solution and answer

Official answer: BSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. In open addressing, to insert a key you follow its probe sequence, examining one slot after another, until you reach an empty slot, and then place the key there.

2. This is exactly the work of an unsuccessful search: that search also follows the probe sequence over occupied slots and stops at the first empty one. So the number of probes for an insertion has the same distribution as for an unsuccessful search; the only extra work is the single write into the empty slot, which is not a probe.

3. The question states that the expected number of probes in an unsuccessful search is at most $\frac{1}{1-\alpha }$. Hence inserting an element needs at most $\frac{1}{1-\alpha }$ probes on average.

4. Check by derivation. Let $X$ be the number of probes. Under uniform hashing, the probability that the first $i$ probes all land on occupied slots is $\frac{n}{m}\cdot \frac{n-1}{m-1}\cdots \frac{n-i+1}{m-i+1}\le {\alpha }^i$, because $\frac{n-k}{m-k}\le \frac{n}{m}$ when $n\le m$. Therefore $E[X]={\sum }_{i\ge 0}P(X>i)\le {\sum }_{i\ge 0}{\alpha }^i=\frac{1}{1-\alpha }$.

5. Check the other options. (D) $\frac{1}{1+\alpha }<1$ for every $\alpha >0$, but at least one probe is always needed, so it cannot be an average. (A) $\ln \frac{1}{1-\alpha }$ equals $0$ at $\alpha =0$ and is below $1$ for $\alpha <1-\frac{1}{e}$, again less than the one probe an insertion always needs. (C) $1+\frac{\alpha }{2}$ stays below $2$, yet the true expected number of probes, $\frac{m+1}{m-n+1}$, grows without limit as $\alpha \to 1$ (for large $m$), so $1+\frac{\alpha }{2}$ cannot be an upper bound.

6. Hence the answer is option (B), $\frac{1}{1-\alpha }$.