[Solved]: What is the result of multiplying O(n) and Ω(n)?

Problem Detail: 

If $f(x) = \Omega(n)$ and $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ?

First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of growth will be same as $n$

But, where I came across this question, the answer given was $\Omega(n)$, and no proof was mentioned. Well, I didn't understand why, but intuitively I convinced myself as "you can't know for sure the upper limit of growth for $f(x) \cdot g(x)$ so you can't say it's $O(n)$, but you can be sure that it won't be lower than $\Omega(n)$"

Can someone help me in understanding this, in a more believable way?

Asked By : sanjeev mk

Answered By : Raphael

Basically, without further information you know nothing about the asymptotic growth of $f \cdot g$.

Let's unfold the definitions:

$\qquad f \in \Omega(n) \implies f(n) \leq cn$ and

$\qquad g \in O(n) \implies g(n) \geq dn$

for some $c,d \in \mathbb{N}$ and $n$ greater than some constant.

Now it's clear that you get no bound on $g \cdot f$; you have no upper bound for one factor and no lower for the other. In fact, you can get arbitrarily slowly and fast growing results:

• For $f : n \mapsto n$ and $g_k : n \mapsto n^{-k}$, we get $f \cdot g_k : n \mapsto n^{-k+1}$. Note that the induced sequence of functions is properly decreasing in terms of asymptotic growth.

• For $f_k : n \mapsto n^k$ and $g : n \mapsto n$, we get $f_k \cdot g : n \mapsto n^{k+1}$. Note that the induced sequence of functions is properly increasing in terms of asymptotic growth.

If you restrict yourself to (eventually) non-decreasing functions -- that is $f,g \in \Omega(1)$ -- you get one of the missing bounds and thus $f \cdot g \in \Omega(n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21575

 Ask a Question

 Download Related Notes/Documents