Hash tables - probing for collisions run time
The average number of positions addressed is 
$$ \frac{1}{2} \left(1 + \frac{1}{1-\alpha}\right) $$
for linear probing and $1 + \alpha/2$ for chained hashing. Here $\alpha$ is the load factor. For each constant $\alpha$, this average is constant, but it depends on $\alpha$. The expression $1/(1-\alpha)$ blows up as the table gets full ($\alpha \to 1$), which is probably what is meant by the dependence is at least linear. The dependence is on the load factor rather than on the absolute number of elements in the table, which is not the deciding factor.

Usually, a linear dependence (not to be confused with the same terminology from linear algebra!) would be $\Theta(\alpha)$, at least linear would be $\Omega(\alpha)$, and more than linear $\omega(\alpha)$; but here $\alpha \to 1$ rather than $\alpha \to \infty$ so terminology is not standard. Perhaps the correct variable, which does go to $\infty$, is $1/(1-\alpha)$. In this case, we do have linear dependence for linear probing.