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

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.

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