If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

192 Views Asked by At

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

From the assumptions, $g(n)$ seems to be an asymptotic tight upper bound for $f(n)$, but do they make $g(n)$ an asymptotic tight lower bound for $f(n)$ as well?

1

There are 1 best solutions below

2
On BEST ANSWER

$f(n) = O(g(n))$ means that $|f(n)| \leq C |g(n)|$, but $f(n) \not\in o(g(n))$ means that you can't make the $C$ as small as you want. If $f(n) = \Theta(g(n))$, it would mean that $|g(n)| \leq D |f(n)|$ for some other bound. What happens if you try $g(n) = 1$ and $f(n) = 0$ if $n$ is even, $f(n) = 1$ if $n$ is odd?