Difference (minus) of asymptotic notations.

Question

$f(n) = 2n^2 + n$

$g(n) = O(n^2)$

The question is to find the mistake in the following process:

$f(n) = O(n^2) + O(n)$

$f(n) - g(n) = O(n^2) + O(n) - O(n^2)$

$f(n)-g(n) = O(n)$

From how I understand it, Big-Oh represents the upper bound on the number of operations (when $n$ tends to very large value). So, the difference between an order of $n^2$ minus an order of $n^2$ should be negligible if $n$ is very large.

But the individual steps seem correct. It seems to me that the mistake is that when doing the minus with large values, the $O(n)$ will also get consumed.

I need clarification on whether I'm correct. If I'm not, then where is the mistake?

Answer 1

Hint

What if $g(n) = n^2$?

What does $f(n) - g(n)$ simplify to, and is it $O(n)$ or $O(n^2)$?

Clarification

With the above, we get $f(n) - g(n) = 2n^2 + n - n^2 = n^2 + n = O(n^2)$.

Remember that, by definition, $f(n) = O(n^p)$ means $f(n) \leq Cn^p$ for some constant $C$ if $n$ large enough. This still holds true for any general $g(n) = O(n^2)$.

Answer 2

According to definition of big-O notation:

$f(x)=O(g(x)){\text{ as }}$$x\to a$\, if and only if

${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }$

$\lim_{x→\infty}\left|{\cfrac {f(n)-g(n)}{(n^2)}}\right|=0$

If $g(x)$ is nonzero, or at least becomes nonzero beyond a certain point, the relation $f(x) = o(g(x))$ is equivalent to

$\lim _{x\to \infty }{\cfrac {f(x)}{g(x)}}=0$.

---

Do you know that,

$f(n)+g(n)=(2n^2+n)+O(n^2)=\max((2n^2+n), O(n^2))=O(n^2)$

Can we conclude that:

$f(n)=g(n)+O(n^2)=O(n^2)$

$f(n)-g(n)=O(n^2)$

Answer 3

When you write $O(h(x))$ (as $x \to \infty$, for some function $h$) you have to imagine that it is written "something (in modulo) which is at most $h(x)$ (up to a constant)", giving you an upper bound for the growth of your function.

This is why, if you write $O(h(x))-O(h(x))$, then it does not simplify to $0$, but it is still $O(h(x))$. You may obtain something "smaller" than $O(h(x))$ only if you have some additional information on what is your first $O(h(x))$ and your second $O(h(x))$.