for positive functions $f(n)$ and $g(n)$, can $f(n)$ be in $\mathcal{O}(g(n))$ and $\Omega(g(n))$?

For positive functions, is it possible for $f(n)$ to be lower bounded by $g(n)$ if its already being upperbounded by $g(n)$? If $f(n) = g(n) = n$, then doesn't that mean $g(n)$ is a lower and upperbound for $f(n)$?

-
I think your understanding is correct. If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, then $f(n) = \Theta(g(n))$ by definition. – Tunococ Jan 27 '13 at 23:54
So if f(n) is in O(g(n)), then f(n) cannot be omega(g(n))? – user59894 Jan 27 '13 at 23:56
That's not what I mean. $f(n) = O(g(n))$ means $f$ does not grow faster than $g(n)$. $f$ may grow as fast as $g(n)$. The same goes for $\Omega$. – Tunococ Jan 27 '13 at 23:58
If $f = O(g)$ then $f \neq \omega(g)$ is a correct conclusion, but you do not know whether $f = \Omega(g)$ or $f \neq \Omega(g)$. – TMM Jan 28 '13 at 0:06
what about if f=O(g) then f≠omega(g)? Is this sometimes true? – user59894 Jan 28 '13 at 0:09

1 Answer

Let $f(n)=n^2+2n$. Then $f(n)\le 2n^2$ for all $n\ge 2$, so $f(n)$ is $O(n^2)$. On the other hand, $f(n)\ge n^2$ for all $n\ge 0$, so $f(n)$ is $\Omega(n^2)$ as well. By definition this means that $f(n)$ is $\Theta(n^2)$.

-
is it possible for g(n) to be strictly an upper bound and lower bound on f(n) no matter what c1, c2 or x0 is given? (like g(n) = f(n) at all times) – user59894 Jan 28 '13 at 0:04
@user59894: That happens precisely when $f$ and $g$ are the same function. – Brian M. Scott Jan 28 '13 at 0:11