1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – G. Bach Feb 12 '14 at 19:45
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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