Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full

Question

to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$ And for $0\leq i,j < \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$ This results into $$(i+j)(i-j) \text{ mod t} = 0$$ Which is a contradiction as either $i+j=0$, $i-j =0$ or $(i+j)(i-j)=t$, and because i and j are chosen to be different and positive the first two can not be. Further t is prime and thus can not be written as a factor.

That is what I got so far. Judging by the Wikipedia entry this should suffice to prove the statement, but I fail to see why this actually shows that it always finds an empty slot. In particular because the fact that i and j are smaller than t/2 is not used at all.

Thank your for your input!

Answer 1

Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i < t/2$ while $j > t/2$. This sort of example cannot happen if $i,j < t/2$, since then $i+j < t$.

Answer 2

Probing doesn’t find an empty slot if all probed slots are full. If less than half the slots are full, and half the slots or more are probed, then you are probing more than the full slots, so the probed slots cannot all be full.