I have a function $f(n)$ that satisfies the following property: for any function $g(n) = o(n^{-2})$, we have $f(n) = \Omega(g(n))$ (the implied proportionality constant in the $\Omega$ expression will, naturally, depend on the function $g$). Is there any easy way to characterize this in this kind of notation, e.g. $f(n) = \Omega(n^{-2})$? (Which I'm guessing isn't true?)
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Assume that $f(n)=o(n^{-2})$. Then $g(n):=n^{-1}\sqrt{f(n)}=o(n^{-2})$, so $f(n)=\Omega(g(n))$, so $\sqrt{f(n)}=\Omega(n^{-1})$, so $f(n)=\Omega(n^{-2})$, a contradiction. This proves that $f(n)=\Omega(n^{-2})$.
P.S. Here I am using the analytic number theory convention of the $\Omega$ notation, as discussed here.
answered Aug 1, 2014 at 2:18
-
1$\begingroup$ It holds for the computer science $\Omega$ just as well by a similar argument. It is only essential that the same reading of $\Omega$ is in force for the premise and the conclusion. $\endgroup$ Commented Aug 1, 2014 at 9:55
-
$\begingroup$ @EmilJeřábek: Thank you! I anticipated this, but I was too sleepy to check. $\endgroup$ Commented Aug 1, 2014 at 12:22