GATE DS&AI 2024 | Question: 11

Question

​​​​​​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.

• A. $\ln \left(\frac{1}{1-\alpha}\right)$
• B. $\frac{1}{1-\alpha}$
• C. $1+\frac{\alpha}{2}$
• D. $\frac{1}{1+\alpha}$

Answer 1

option b is ryt since it will take time proportional to search first and then constant time for insertion.