1
$\begingroup$

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)

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I agree with the first example but not the second: suppose $g(x)=x^4=\Omega(x)$. I agree that the expression is 'ambiguous' in the sense that it may not be possible to combine the $\Omega(\cdot)$ and the $O(\cdot)$ to obtain a single expression for $f(x)$, but I am asking whether or not it is permissible to add sets of functions together in the manner I proposed (I don't see why it wouldn't be). Thanks $\endgroup$
    – nknight
    Apr 26, 2013 at 22:20
  • $\begingroup$ IF $g(x)=\Omega(x^4)$, then $f(x)=\Omega(x^4)$. Expression $f(x)=\Omega(x^4)+O(x^4)$ doesn't make sense. It is sensible to say that $f(x)=O(x^4)$ AND $\Omega(x^4)$, then $f(x)=\Theta(x^4)$ $\endgroup$
    – Alex
    Apr 26, 2013 at 23:47
  • $\begingroup$ I still feel like the set of functions $\Omega(x)-O(x^3)$ is a subset of $\Omega(x^3)$, not $O(x^3)$, if you interpret the '$-$' operation as set difference. However, I originally intended the '$-$' operation as denoting the set of pairwise differences, e.g., $\{g-h:g(x)\in\Omega(x),h(x)\in O(x^3)\}$, which contains (e.g.) $f(x)=0$, and this is clearly incompatible with the set difference interpretation, thus ambiguous. $\endgroup$
    – nknight
    Aug 6, 2013 at 3:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .