I came upon the need to multiply two function run-times: $\Omega(f)*\Omega(g)$.
On wikipedia, such product exists for Big-Oh notation (and equals $O(f*g)$), but the $\Omega$ page is very lacking.
I couldn't find anywhere online (including "Asymptotic Methods in Analysis" by De Bruijn, but maybe I missed it?) any mention for existance on this property for $\Omega$, let alone a proof for it.
I see no reason why Omega should be any different from O, but the fact that I couldn't find any reference to it kind of bugs me.
Could someone please refer me to a page on the subject, or simply confirm this property?
Best Answer
It does have the same property. Suppose $f=\Omega(f_1)$ and $g=\Omega(g_1)$, all positive functions. There exist constants $c,d\geq 0$ and $A,B\geq 0$ such that for $x\geq c$, $f(x)\geq Af_1(x)$ and for $x\geq d$, $g(x)\geq Bg_1(x)$. Choosing c=$\max(c,d)$, if $x\geq c$, we have $f(x)g(x)\geq ABf_1(x)g_1(x)$. So $fg=\Omega(f_1g_1)$ as you want.