# Difference (minus) of asymptotic notations.

$$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?

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)$.

• Doesn't it simplify to zero since both represent approximate number of operations (or whatever we are measuring)? I mentioned that in the question but it seems you are trying to say something else. In case you are trying to say that they add up, I had thought of the same at first when I was thinking in terms of problems or algorithms. Can you please clarify how it ends up being added up? Aug 18, 2016 at 11:17
• @aste123 I added the conclusions to the hint, hope that helps. Aug 18, 2016 at 11:35
• Thanks but where is the mistake in the steps highlighted in the question? Since we are dealing with order of magnitudes isn't 2n^2 - n^2 = 0 if the value of n is very large (close to infinity)? Aug 18, 2016 at 11:41
• @aste123 Oh I understand what you are saying now. It is true that the fraction $2n^2 / n^2$ is finite, meaning both numerator and denominator grow at the same rate ($O(n^2)$ obviously) - but the difference $2n^2 - n^2$ is itself of the order $O(n^2)$, since $2n^2 - n^2 = n^2$, and so the difference grows to infinity as $n \to \infty$. Aug 18, 2016 at 11:44

According to definition of big-O notation:

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

$\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)$

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))$.