1

Is the following true. $$\frac{O(f(x))}{O(g(x))}=O\left(\frac{f(x)}{g(x)}\right)$$

If not under what conditions is it?

For example, the function,

$$h(x)=\frac{x^3+2x}{2x+1}$$ has $O(x^3)/O(x)$. And the total function has $O(x^2)$. My concern is that $2x+1$ can have $O(x^n)$ for $n\geq 1$. Thus making it seem false. Perhaps the big theta notation has this property.

John
  • 1,149

2 Answers2

3

We have $O(f(x)) O(g(x)) = O(f(x) g(x))$. In words: a function that is at most a constant times $f(x)$, multiplied by a function that is at most a constant times $g(x)$, is at most a constant times $f(x) g(x)$. (We assume that $f$ and $g$ are positive functions, so that we can say "at most" instead of "in absolute value at most".)

(Note that when dealing with $O$ notation, the "$=$" sign is like the English "is", and is not necessarily symmetric: if you wish, you can view each side as the set of functions of that type, and replace the "$=$" with "$\subset$". But in this case it's also true that $O(f(x) g(x)) = O(f(x)) O(g(x))$.)

Also we have $$g(x) = \Omega(h(x)) \iff \frac{1}{g(x)} = O\left(\frac{1}{h(x)}\right)$$ (again, assuming the functions are positive, etc.)

So the right statement is that

$$\frac{O(f(x))}{\Omega(g(x))} = O\left(\frac{f(x)}{g(x)} \right)$$

in your case, what matters is not that $2x + 1 = O(x)$, but that $2x + 1 = \Omega(x)$.

That it is also true with $\Theta$ is a corollary.

ShreevatsaR
  • 41,374
2

$$x^4\in O(x^5)\quad x\in O(x^3)\quad\frac{x^4}x\notin O\left(\frac{x^5}{x^3}\right)\quad (x\to\infty)$$ $$ f\in\Theta(F)\quad\&\quad g\in\Theta(G)\implies\frac{f}g\in\Theta\left(\frac{F}G\right)$$

Did
  • 279,727
  • Thanks. I expressed a similar concern in the question, I am wondering for what conditions can it be true and if it applies to the big - theta notation. – John Mar 30 '14 at 08:09
  • 2
    With $O$, no chance. With $\Theta$, trivially true (just write down the definitions). – Did Mar 30 '14 at 08:10
  • Your statement is only true for $O(f)=O(0)$. Otherwise it's false. –  Mar 30 '14 at 08:11
  • This obviously includes the fact that $g\neq 0$ and $G \neq 0$. – John Mar 30 '14 at 08:13