When is a bound asymptotically tight?

Question

What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight.

The definitions of O-notation and o-notation are similar. The main difference is that in $f(n) = O(g(n))$, the bound $0 \leq f(n) \leq cg(n)$ holds for some constant, $c>0$, but in $f(n) = o(g(n))$, the bound $0 \leq f(n) < cg(n)$ holds for all constants, $c>0$.

So what is the difference in big-O notation and small-o notation?

Answer 1

We say that a bound $f(n) = O(g(n))$ is tight if in fact $f(n) = \Theta(g(n))$, that is, if also $g(n) = O(f(n))$. So $2n^2 = O(n^2)$ is tight since $n^2 = O(2n^2)$, whereas $2n = O(n^2)$ is not tight since $n^2 \neq O(2n)$.

As you mention in your question, if $f(n) = o(g(n))$ then the bound $f(n) = O(g(n))$ is not asymptotically tight. However, there is a third option: it could be that $f(n) = O(g(n))$, $f(n) \neq o(g(n))$, and yet the bound $f(n) = O(g(n))$ is not asymptotically tight. An example is $f(n) = n|\sin n|$ and $g(n) = n$.

One could also define $f(n) = O(g(n))$ to be tight if $f(n) \neq o(g(n))$. In that case the "third option" is that $f(n) = O(g(n))$ is asymptotically tight although $f(n) \neq \Theta(g(n))$.