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

71 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST 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)$.