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)$?
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.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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)$.