4
$\begingroup$

We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$.

So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$?
Then what is $\Theta(f(n)+g(n))$ equal to?

$\endgroup$
8
$\begingroup$

Assuming $f,g > 0$, we have $$\max(f(x),g(x)) < f(x) + g(x) \leq 2\max(f(x),g(x)).$$ Therefore $\Theta(f(x) + g(x)) = \Theta(\max(f(x),g(x)))$, in the sense that both sets of functions are equal.

Still assuming that $f,g > 0$, it is also true that $\Omega(f(x)+g(x)) = \Omega(\min(f(x),g(x)))$, in the sense that if $h(x) \in \Omega(f(x)+g(x))$ then also $h(x) \in \Omega(\min(f(x),g(x))$. The stronger bound $\Omega(f(x)+g(x)) = \Omega(\max(f(x),g(x)))$ also holds.

I have mentioned two interpretations of equality. In fact the second one (which really corresponds to $\subseteq$ in this case) is actually the standard one – equality is not symmetric! However, in the case of big $\Theta$ both notions fortunately coincide.

$\endgroup$
  • $\begingroup$ Thanks for making this clear ! So ultimately both Ω(min(f(x),g(x)) and Ω(max(f(x),g(x))) holds right? $\endgroup$ – bandit_king28 Dec 19 '15 at 5:43
  • 2
    $\begingroup$ That's exactly right. $\endgroup$ – Yuval Filmus Dec 19 '15 at 7:45
  • 1
    $\begingroup$ I think you should be able to answer such questions yourself now. $\endgroup$ – Yuval Filmus Dec 19 '15 at 11:09
  • $\begingroup$ Please fix, @RickyDemer's answer looks correct to me (and disagrees with your's). $\endgroup$ – vonbrand Jan 13 '16 at 1:43
  • $\begingroup$ @vonbrand We have different interpretations of $=$. $\endgroup$ – Yuval Filmus Jan 13 '16 at 6:26
1
$\begingroup$

"So can we say that $\Omega(f(n)+g(n)) = \Omega(\min(f(n),g(n))$?"

No. (Consider 1 and n.)

"Then what is $\Theta(f(n)+g(n))$ equal to?"

If $f$ and $g$ can have opposite signs then $O(\max(f(n),g(n)))$, else $\Theta(\max(f(n),g(n)))$.

$\endgroup$
  • $\begingroup$ then what is Ω (f(n)+g(n))? $\endgroup$ – bandit_king28 Dec 18 '15 at 11:44
  • $\begingroup$ f(n)=Ω(n) and g(n)=Ω($n^2$) then what is the value of Ω(f(n)+g(n)). $\endgroup$ – bandit_king28 Dec 18 '15 at 12:03
  • 1
    $\begingroup$ I guess the "No" answers the first question mark, and the second line answers the second one. However, this is not immediate, and this answer should be expanded to provide more context. $\endgroup$ – chi Dec 18 '15 at 12:13
  • $\begingroup$ Can u help me with the above question? I explicitly stated what f(n) and g(n) is ! I am currently having problems grasping the concept! @Ricky Demer $\endgroup$ – bandit_king28 Dec 18 '15 at 12:18
  • 2
    $\begingroup$ @user3932852 : ​ We only care about the dominant term, but even for Ω, the dominant term is still the maximum. ​ ​ ​ ​ $\endgroup$ – user12859 Dec 18 '15 at 22:44

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.