Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1\), where \(n\) elements are stored in the table with \(m\) slots. The expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\).
Inserting an element in this hash table requires at most ______ probes, on average.
Answer
(B)
Explanation
To insert a key with open addressing, we follow the key's probe sequence until we reach an empty slot and store the key there. An unsuccessful search for the same key follows the same sequence and also stops at the first empty slot, so an insertion makes exactly the probes of an unsuccessful search. Its average cost therefore has the same bound, at most \(\frac{1}{1-\alpha}\) probes.
Options A and C are smaller than this bound for every \(0 < \alpha < 1\), so they understate the cost; they resemble formulas for successful searches. Option D is even below 1, although every insertion probes at least one slot.
Answer: B