-1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ isn't f(n) ≤ h(n) so why can't we write it as 𝑓(𝑛)+𝑔(𝑛)≤f(𝑛)≤𝑐⋅ℎ(𝑛) for all 𝑛≥𝑛0. $\endgroup$
    – user159086
    Mar 7, 2023 at 14:00
  • $\begingroup$ $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$). $\endgroup$
    – Steven
    Mar 7, 2023 at 14:06
  • $\begingroup$ if h(n) = n shouldn't O(h)= n^2 or something bigger? $\endgroup$
    – user159086
    Mar 7, 2023 at 14:11
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Mar 7, 2023 at 14:36
1
$\begingroup$

$f+g$ being larger than $g$, the lower bound of $g$ still holds. And we know nothing about the upper bound.

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