3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Ordoshsen Oct 9 '19 at 11:39
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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.