Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
The stated answer of $\Omega(n)$ is wrong (assuming $o(1)$ functions are allowed for $g$); $g(n) = 0$ would put $g$ safely in $O(n)$. –  G. Bach Feb 12 at 19:45
add comment

1 Answer

up vote 10 down vote accepted

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)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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