Landau big $\Omega$ notation

112 Views Asked by At

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

1

There are 1 best solutions below

1
On

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.