Suppose that $f(x)$ and $g(x)$ are two non negative functions and suppose that $$f(x)=O(g(x)).$$ Can we conclude that $$-g(x)=O(-f(x)) ?$$ I think is false but i'm not sure. Thank you and sorry for this dumb question.
Asked
Active
Viewed 126 times
0
-
No: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition – Did Nov 21 '13 at 12:09
-
Remember that $O(\cdot)$ is only concerned with the absolute value of the functions involved. Have you tried any examples? – Antonio Vargas Nov 21 '13 at 12:27
2 Answers
0
$$\begin{align*} |f(x)| & \le C |g(x)| \\ \Rightarrow -C |g(x)| & \le -|f(x)| \\ \not\Rightarrow |g(x)| & \le C^{-1} |f(x)| \end{align*}$$ So the answer is no, since $\mathcal O$ refers to the absolut value of a function.
AlexR
- 24,905
-
-
@AntonioVargas Thank you :) I forgot the sign change from swapping the sides^^ – AlexR Nov 21 '13 at 12:31
0
Even with the right signs this is false. For example, for $x>1$, we have that $1=O(x)$, but $x\neq O(1)$.
