0


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?

yoad w
  • 151

1 Answers1

0

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.

Arkady
  • 9,315
  • Okay, I think I got. And your answer gave me the idea on how to write further proofs on my own. 1) how do I answer this question page? 2) shouldn't the inequality be >=, since omega is the lower bound? – yoad w Apr 02 '16 at 10:35
  • @yoadw You are totally correct, but note that all I had to do to make my proof right was to change the $\leq$ to $\geq$. I do not understand your first question though – Arkady Apr 02 '16 at 13:31