GATE CS 1989 Q1-vii — Searching, Sorting, Hashing

In a hash table with linear probing, an unsuccessful search for a key starting at index $i$ continues probing consecutive slots until an empty slot is encountered.

The number of comparisons required for an unsuccessful search starting at index $i$ is equal to the number of consecutive occupied slots starting from $i$, plus $1$ (for the final comparison with the empty slot that terminates the search).

In the given hash table, the longest contiguous block of occupied slots has a length of $4$ (slots $0$ to $3$ containing $S_1, S_2, S_3, S_4$, followed by an empty slot at index $4$).

The maximum number of comparisons occurs when a searched key hashes to index $0$:

• Probe 1: Index 0 (occupied by $S_1$)
• Probe 2: Index 1 (occupied by $S_2$)
• Probe 3: Index 2 (occupied by $S_3$)
• Probe 4: Index 3 (occupied by $S_4$)
• Probe 5: Index 4 (empty slot — search terminates)

Thus, the maximum number of comparisons needed is 5.