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.

$\endgroup$
7
  • $\begingroup$ The answer to your previous question also answers this. Don't cheat by changing your ID. $\endgroup$
    – user16034
    Commented Mar 23, 2023 at 13:07
  • 1
    $\begingroup$ Does this answer your question? If f = O(h) and g = Ω(h) then f+g is? $\endgroup$
    – user16034
    Commented Mar 23, 2023 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$ Commented Mar 23, 2023 at 14:04
  • $\begingroup$ Anyway, the other post does answer. $\endgroup$
    – user16034
    Commented Mar 23, 2023 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$ Commented Mar 24, 2023 at 8:49

2 Answers 2

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

$\endgroup$
1
  • $\begingroup$ Great, thanks so much! $\endgroup$ Commented Mar 24, 2023 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)).

$\endgroup$

Your Answer

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

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