# How to prove asymptotic property with big O notation?

Could you help me to show: $g(x,\epsilon)+f(x,\epsilon)=O(|\phi(x,\epsilon)|+|\psi(x,\epsilon)|)$ but $g(x,\epsilon)+f(x,\epsilon)\neq O(\phi(x,\epsilon)+\psi(x,\epsilon))$ (both when $\epsilon\to0$), where $O$ stands for the big Oh notation?

-
I suppose the assumption is that $g(x,\epsilon)=O(\phi(x,\epsilon))$ and likewise for $f$ with $\psi$? – Raskolnikov Feb 21 '11 at 18:47
Try $f(x)=g(x)=\phi(x)=x$ and $\psi(x)=-x$. – Yuval Filmus Feb 21 '11 at 19:02

So, assuming $g(x,\epsilon)=O(\phi(x,\epsilon))$ and $f(x,\epsilon)=O(\psi(x,\epsilon))$ this means that $\exists \delta_1,\delta_2,M_1,M_2$ such that

$$\forall |\epsilon|<\delta_1 : |g(x,\epsilon)| < M_1 |\phi(x,\epsilon)|$$

and

$$\forall |\epsilon|<\delta_2 : |f(x,\epsilon)| < M_2 |\psi(x,\epsilon)| \; .$$

This implies that

$$\begin{eqnarray} \forall |\epsilon| < \min(\delta_1,\delta_2) : & |g(x,\epsilon) + f(x,\epsilon)| & \leq |g(x,\epsilon)| + |f(x,\epsilon)| \\ & & < \max(M_1,M_2)(|\phi(x,\epsilon)| + |\psi(x,\epsilon)|) \; , \end{eqnarray}$$

using the triangle inequality. Or in other words $g(x,\epsilon)+f(x,\epsilon)=O(|\phi(x,\epsilon)|+|\psi(x,\epsilon)|)$.

Now, using Yuval Filmus' suggestion, you can see that for the choice $f(x)=g(x)=\phi(x)=x$ and $\psi(x)=-x$, $2x=O(2|x|)$, which is correct. The other identity can not be correct however since $2x \neq O(0)$.

-