0
$\begingroup$

If $f_1(x)$ and $f_2(x)$ are functions from the set of positive integers to the set of positive real numbers and $f_1(x)$ and $f_2(x)$ are both $\Omega(g(x))$, is $(f_1 − f_2)(x)$ also $\Omega(g(x))$?

How do I prove/disprove this?

1 Answers 1

1

No. It is not. For instance, consider $f_1(x) = f_2(x) = x^2$ and $g(x) = x$.

For a slightly non-trivial example, consider $f_1(x) = x^3 + x^2 + x + 1, f_2(x) = x^3 + x^2 + 1 \text{ and }g(x) = x^2$ We have $f_1(x),f_2(x) \in \Omega(g(x))$ but $f_1(x) -f_2(x) = x \notin \Omega(g(x))$.