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
