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 &lt; \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!
Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i &lt; t/2$ while $j &gt; t/2$. This sort of example cannot happen if $i,j &lt; t/2$, since then $i+j &lt; t$.