$O(f)-g = O(f-g)$: asymptotics of difference of functions

45 Views Asked by At

I have given three functions $f$, $g$, $h$ where it might be relevant that all these functions are bounded from above by $1$.

I know that $$|f-g|=d$$ where $d$ may depend on $n$ and I know that $$h(n)=O(f(n)).$$

Now I'd like to find $|h-g|$.

Is it true that

$$|h-g|=|O(f)-g|=|O(f-g)|=O(|f-g|)=O(d)?$$

I know that $f=g=h=d=O(1)$, but this is not what I want to prove. I want to prove that e.g. if $d=\frac{1}{n}$ that then $|h-g|=O(\frac{1}{n})$.

It might be of interest why I ask this question: when I say that $h(n)=r(n) f(n)$ where $r(n)=O(1)$, then I get

$$|h-g|=|rf-g|=|r(f-g)+g(r-1)|\leq |r||f-g|+ |g||r-1| =O(d)+O(g)$$

BUt this does not have to be the same as $O(d)$. So which one is the correct (the better) solution?

REMARK: I'm not sure how $=O(...)$ is used, but I use $=O(...)$ interchangaably with $\in O(...)$. If this helps to avoid some confusion.

1

There are 1 best solutions below

3
On BEST ANSWER

No, $O(f)-g\ne O(f-g)$ in general, and the case $f=g$ should help as a warning.

What is true however is that $O(f)-g\subseteq O(|f|+|g|)$ in the sense that, if $h\in O(f)$ then $h-g\in O(|f|+|g|)$.

Edit: If $h\in O(f)$ and $d=|f-g|$ then $|h-g|\leqslant|h-f|+d\leqslant|h|+|f|+d$ hence $|h-g|\in O(|f|+d)$.

And the inequality $|f|\leqslant d+|g|$ shows that $O(|f|)=O(f)\subseteq O(d+|g|)=O(d)+O(g)$ hence $|h-g|\leqslant|h|+|g|$ implies that $|h-g|\in O(d)+O(g)$.