# When is a bound asymptotically tight?

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 deﬁnitions 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?

• This is two separate questions and should be asked as such. The Stack Exchange format doesn't work very well with more than one question in a post, unless those questions are very closely related (which these aren't). – David Richerby Mar 27 '17 at 18:46

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))$.

• Great answer. Thank you. – David Kariuki Dec 5 '19 at 17:40