11-3 Quadratic probing

Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \ldots, m - 1$, and suppose that we have a hash function $h$ mapping the key space into the set $\{0, 1, \ldots, m - 1\}$. The search scheme is as follows:

1. Compute the value $j = h(k)$, and set $i = 0$.
2. Probe in position $j$ for the desired key $k$. If you find it, or if this position is empty, terminate the search.
3. Set $i = i + 1$. If $i$ now equals $m$, the table is full, so terminate the search. Otherwise, set $j = (i + j) \mod m$, and return to step 2.

Assume that $m$ is a power of $2$.

a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants $c_1$ and $c_2$ for equation $\text{(11.5)}$.

b. Prove that this algorithm examines every table position in the worst case.

(Removed)