Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An alternative way to write this condition is to ask that $\{1, \ldots, N\} \subseteq A-A$.) For example, for $N=9$, we could take $A=\{-3, -2, -1, 0, 3, 6\}$, which achieves $|A|=6$.

It easy to see that $|A| \geq \sqrt{2N}$, as at most $\binom {|A|} 2 \leq |A|^2/2$ differences can be formed from the elements of $A$. I can also construct suitable sets $A$ with $|A| = 2 \sqrt N$.

Is the lower bound $\sqrt{2N}$ asymptotically correct? If not, what is the correct lower bound?