Examples of non-sparse languages
For a language&nbsp;$L$, let's write $\|L\|_n$ for the number of length-$n$ strings it contains.  So $L$&nbsp;is sparse if there is a polynomial&nbsp;$p$ such that $\|L\|_n\leq p(n)$ for all&nbsp;$n$. The key point is that, for a language to be sparse, we must be able to pick just one polynomial that works for all&nbsp;$n$: you're not allowed to use a different polynomial for each&nbsp;$n$.

For example, suppose that you wanted to prove that the language of strings over $\{0,1\}$ with at most two $1$s is sparse.  You can't say "Well, for $n=3$, there are seven valid strings, and $7 &lt; n+5$ for $n=3$. And for $n=4$, there are eleven valid strings, and $11 &lt; n^2-4$ for $n=4$, and..." You have to pick just one polynomial that works for all values of&nbsp;$n$: in this case, $n^2$ works, so the language is sparse.

So, for a non-sparse language, $\|L\|_n$, when considered as a function of&nbsp;$n$, must grow faster than any possible polynomial. The simplest examples of functions that grow faster than polynomials are exponentials. Conveniently, $\{0,1\}^*$ has $\|\{0,1\}^*\|_n=2^n$ for all&nbsp;$n$. So, whatever polynomial&nbsp;$p$ you pick, $\|\{0,1\}^*\|_n&gt;p(n)$ for all large enough&nbsp;$n$. Therefore, $\{0,1\}^*$ is not sparse.

Another example of a non-sparse language is the complement of a sparse language. If $\|L\|_n\leq p(n)$ for all&nbsp;$n$, then $\|\overline{L}\|_n\geq 2^n-p(n)$ and this grows faster than any polynomial if $p$&nbsp;is a polynomial.