0
$\begingroup$

I have seen a table of Landau notation definitions which defines $$f \in \Omega(g) \iff \exists k, N > 0 \colon \forall  n > N, \,f(n) \geq k \,g(n)$$

But every other definition in the table puts the $f$ and $g$ in their respective rhs analogs each in absolute values and writes the respective inequalities so that they are strict. If we did so here, then the rhs would read "$|f(n)| > k |g(n)|$" instead of the present "$f(n) \geq k \,g(n)$".

I like this more because it maintains symmetry. However, it is not technically equivalent if, for example, $\exists N > 0 \colon \forall n > N, g(n) < 0$. But I have never come across such a bound in practice. Elaborating on that particular case, any eventually-nonnegative function would be $\Omega$ of any eventually-negative function, which seems useless. But maybe I am not seeing some other situation in which this freedom is nice to have, particularly if equality is permitted.

So, my question is whether there is any practical utility in intentionally failing to require both that $g$ be nonnegative and that the inequality be strict (prohibiting the possibility of equality). Can we alter the definition in the table so that "$g(n)$" be replaced with "$|g(n)|$" and "$\geq$" be replaced with "$>$"?

$\endgroup$
2
  • $\begingroup$ Where did you see that definition? Perhaps $f$ and $g$ are assumed to be non-negative in the context of your definition? $\endgroup$ – Martin R Feb 23 at 8:34
  • $\begingroup$ I agree with @MartinR ... I would write $\Omega(g)$ only if $g$ is (eventually) positive. Note that if $g=0$ sometimes [like $\sin x$], then the definitions with $>$ and with $\ge$ are not equivalent. But if $g$ is positive, then they are equivalent. $\endgroup$ – GEdgar Feb 23 at 12:49
0
$\begingroup$

There are several definitions of the "Landau" notations floating around. Look at how it is used, you might see that the author has only the case $f, g$ positive in mind. This definition of $\Omega$ makes little sense otherwise anyway.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.