# If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?

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.

– user16034
Mar 23 at 13:07
• Does this answer your question? If f = O(h) and g = Ω(h) then f+g is?
– user16034
Mar 23 at 13:08
• 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)). Mar 23 at 14:04
• Anyway, the other post does answer.
– user16034
Mar 23 at 15:14
• 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? Mar 24 at 8:49

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