1
$\begingroup$

It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).

Someone suggested that this question answers mine, which it doesn't. As I've written above, proving that f(n) + g(n) ∈ Ω(h(n)) is easy. I am having trouble disproving that f(n) + g(n) ∈ O(h(n)).

Thanks for any help.

Improve this question
$\endgroup$
7
  • $\begingroup$ The answer to your previous question also answers this. Don't cheat by changing your ID. $\endgroup$
    – user16034
    Mar 23 at 13:07
  • 1
    $\begingroup$ Does this answer your question? If f = O(h) and g = Ω(h) then f+g is? $\endgroup$
    – user16034
    Mar 23 at 13:08
  • $\begingroup$ What do you mean? I created this profile today and I've never asked a question before. As far as that link answering my question, it doesn't. As I've written in the post, I can easily prove that f(n) + g(n) ∈ Ω(h(n)), but I am unable to disprove that f(n) + g(n) ∈ O(h(n)). $\endgroup$
    – figsinwinter
    Mar 23 at 14:04
  • $\begingroup$ Anyway, the other post does answer. $\endgroup$
    – user16034
    Mar 23 at 15:14
  • $\begingroup$ The post answers only one half of my question. In order for f(n) + g(n) ∈ Θ(h(n)) to hold, I need to prove that f(n) + g(n) ∈ Ω(h(n)) AND f(n) + g(n) ∈ O(h(n)). The other post proves only the first part, but it doesn't prove/disprove the second part. Do you see my issue? $\endgroup$
    – figsinwinter
    Mar 24 at 8:49

2 Answers 2

Reset to default
1
$\begingroup$

"We know nothing about the upper bound" is a good intuition but it is not a formal proof that you can't hope to show $f(n) + g(n) \in O(h(n))$ if your only assumptions are $f(n) \in O(h(n))$ and $g(n) \in \Omega(h(n))$.

Fortunately, a counterexample is easily obtained by considering, e.g., $f(n)=1$, $g(n)=n^2$, and $h(n)=n$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great, thanks so much! $\endgroup$
    – figsinwinter
    Mar 24 at 12:50
1
$\begingroup$

Thanks to Yves Daoust for providing the answer. We know nothing about the upper bound of f(n) + g(n) so we cannot prove f(n) + g(n) ∈ O(h(n)).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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