0
$\begingroup$

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

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – aste123
    Aug 18, 2016 at 11:17
  • $\begingroup$ @aste123 I added the conclusions to the hint, hope that helps. $\endgroup$
    – naslundx
    Aug 18, 2016 at 11:35
  • $\begingroup$ 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)? $\endgroup$
    – aste123
    Aug 18, 2016 at 11:41
  • 1
    $\begingroup$ @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$. $\endgroup$
    – naslundx
    Aug 18, 2016 at 11:44
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.