# If f = O(h) and g = Ω(h) then f+g is?

Is the answer O(h) or Ω(h) for f+g? My professor says its Ω(h), but I can't get it.

I'm going to assume that $$f(n)$$ is non-negative.
From $$g(n) \in \Omega(h(n))$$ you know that there is some $$n_0$$ and some $$c$$ such that, for all $$n \ge n_0$$, $$g(n) \ge c \cdot h(n).$$ Then: $$f(n) + g(n) \ge g(n) \ge c \cdot h(n) \quad \text{ for all } n \ge n_0.$$ Therefore $$f(n)+g(n) \in \Omega(h(n))$$.
• $f(n) + g(n) \le f(n)$ is false for all $g(n)$ that are not asymptotically $0$. Pick $f(n) = 1$, $g(n) = n^2$, and $h(n) = n$ as an example and check where it breaks down (you can use, e.g., $n_0=1$ and $c=1$). Commented Mar 7, 2023 at 14:06
• I don't know what $O(h)=n^2$ means. $O(h(n))$ denotes a set of functions. $f(n) = O(h(n))$ is a common abuse of notation for $f(n) \in O(h(n))$. It makes no sense to say that a set is equal to a function. $O(h(n))$ is the set of all functions $z(n)$ such that $z(n) \le c \cdot h(n)$ for some constant $c \ge 0$ and for all sufficiently large $n$. Commented Mar 7, 2023 at 14:36
$$f+g$$ being larger than $$g$$, the lower bound of $$g$$ still holds. And we know nothing about the upper bound.