Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.