Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.