# Find the error in the following “proof” that $O(n) = O(n^2)$

Let $$f(n) = n^2 , g(n) = n$$, and $$h(n) = g(n)−f(n)$$. It is clear that $$h(n) ≤ g(n) ≤ f(n)$$ for all $$n ≥ 0$$. Therefore, $$f (n) = \max(f (n), h(n))$$. Thus, $$O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n), h(n))) = O(f(n)) = O(n^2)$$.

Can you explain why this statement is wrong?

• Also g(n) < f(n) only for n > 1. It makes no difference in the grand scheme, but one of your assumptions is not entirely correct Oct 9 '19 at 11:39

You're basically claiming that $$O(n^2+n-n^2)$$ is the same thing as $$O(n^2)$$, and that's not true.

Depends on what you mean when you write $$O(a(n)) = O(b(n))$$.

Do you mean that the two set of functions are identical or are you using the (common) abuse of notation to mean $$O(a(n)) \subseteq O(b(n))$$?

In the former case this is wrong: $$O(f(n) + h(n)) = O(\max(f(n), h(n)))$$. Notice that the first term is $$O(n)$$ by definition of $$h(n)$$, while the second term is $$O(n^2)$$ since the maximum is always attained by $$f(n)$$. Clearly, the sets of functions $$O(n)$$ and $$O(n^2)$$ do not coincide. For example $$n^{3/2} \not\in O(f(n) + h(n))$$ but $$n^{3/2} \in O(\max(f(n), h(n)))$$.

In the second case nothing is wrong. In fact, it is true that $$O(n) \subseteq O(n^2)$$.

Let $$d(n) \in O(n)$$ and notice that, by definition of $$O(\cdot)$$, there exist two constants $$n_0 \ge 1$$ and $$c > 0$$ such that $$\forall n \ge n_0$$, $$d(n) \le c n$$. But then $$d(n) \le c n \le c n^2$$, showing that $$d(n) \in O(n^2)$$.

Because $$h(n)$$ is negative, as soon as $$n\geq 2$$ your argument does not work. Complexities are supposed to be nonnegative and $$a(n)=O(b(n))$$ requires $$a(n)\leq cb(n)$$ where $$c>0$$ is a constant.

• The arguments of in the big-oh notation of the original post are all non-negative. Oct 9 '19 at 1:11