Does proving that a function is not in big O mean that the function is in big Omega?

Question

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?

Answer 1

No, you cannot, at least under the definition of big-$\Omega$ used in computer science.

For example: $f(n) = n^2$ if $n$ is of the form $\displaystyle 2^{4^k}$ and $f(n) = f(n-1)$ otherwise; $g(n) = n$. Then $f(n)$ is as large as $n^2$ infinitely often, so $f(n)$ is not $O(g(n))$. Also, $f(n)$ is smaller than $2\sqrt{n}$ infinitely often (for instance, when $n=2^{4^k}-1$, $f(n) = (2^{4^{k-1}})^2 = 2^{2^{2k-1}} = \sqrt{2^{4^k}} = \sqrt{n+1} < 2\sqrt{n}$), so $f(n)$ is not $\Omega(g(n))$.

Note: this example is a bit complicated because I wanted both functions to be nondecreasing. If you allow all functions and not just monotone ones, a counterexample is even easier: $f(n) = n^2$ for $n$ even and $f(n) = 1$ for $n$ odd, while $g(n) = n$.