Mixing asymptotic notations

192 Views Asked by At

I have a function $f(x) = g(x) - h(x)$ and I know that $g(x)=\Omega(\hat g(x))$ and $h(x)=O(\hat h(x))$. Is it well-defined to express this in asymptotic notation, as $f(x) = \Omega(\hat g(x))-O(\hat h(x))$?

More generally, are there any restrictions on using two or more distinct $\{o,O,\Theta,\Omega,\omega\}$-notations in the same expression?

(Related: Set operations on asymptotic notations)

1

There are 1 best solutions below

3
On BEST ANSWER

$\Omega(g(x)) -O(h(x))$ is quite an ambiguous expression. If, e.g. $g(x) = \Omega(x^2)$ and $h(x) = O(1)$, then $f(x)=\Omega(x^2)$. If, on the other hand, $g(x) = \Omega(x)$ and $h(x) = O(x^3)$, then $f(x) = O(x^3)$