Constructing a small set of numbers whose differences cover $\{1,\ldots,n\}$

Question

Let $n\in\mathbb N$.

Given a set $S\subset\mathbb N$, let $\Delta(S) = \{a-b\mid a,b\in S\}$ denote its set of differences.

I'm interested in finding a small set $S_n$ such that $\{1,\ldots,n\}\subseteq\Delta(S_n)$.

For example, if $n=8$ we can use

$$S_8 =\{1,2,4,8,9\}. $$

How can we construct a small $S_n$ efficiently? (Efficiently should ideally be $O(|S_n|)$ time, but any $o(n)$ time would be interesting.)

How does the smallest $|S_n|$ grow as a function of $n$? (As a guess, I'd like to say $|S_n|=O(\sqrt n)$ should be possible?)

Answer 1

One example of such a set is $S_n = \{0,1,2,\dots,k\} \cup \{k,2k,3k,\dots,k^2\}$ where $k=\lceil \sqrt{n} \rceil$. It follows that $|S_n|=O(\sqrt{n})$, and $S_n$ can be constructed in $O(\sqrt{n})$ time.

See also https://math.stackexchange.com/q/168079/14578.