$$ f_1(n) = n^2 $$ $$ f_2(n) = n^2 + 1000n $$

Are the following statements true or false? $$ f_1(n) = O (f_2(n)), $$ $$ f_2(n) = O (f_1(n)), $$ Based on what I know about big O notation, I think the first statement is true and the second false, however my answer sheet says they're both true. Is that correct?

  • $\begingroup$ Why don't you go by definition. $\frac{f_1(n)}{f_2(n)} =\frac{n^2}{n^2+1000n}$ will this be less than a constant for all n? But the other way round, $\frac{f_2(n)}{f_1(n)} =\frac{n^2+1000n}{n^2} $ how about this? $\endgroup$ – S.Dan Mar 9 '15 at 4:44
  • $\begingroup$ @S.Dan Since the limit as n approaches infinity is 1 for both then both will be less than a constant for all n, meaning both statements are true, right? $\endgroup$ – hildk Mar 9 '15 at 5:01

You have to think carefully the definition of the $O$-notation:

$f(n) = O(g(n))$ if and only if there exists a constant $c>0$ and $N \in \mathbb{N}$ such that $$ f(n) \le c\cdot g(n), \quad \forall n \ge N. $$ Note that you need two things: the constant $c$ and $N$. The definition does not require that the inequality $f(n) \le c\cdot g(n)$ holds for all $n$. It requires that it holds for sufficiently large $n$.

In your example, it is easy to see that $f_{1}(n) = O(f_{2}(n))$, because $f_{1}(n) \le 1\cdot f_{2}(n)$, and that happens to hold for all $n$.

What about the second relation? Can you find appropriate $c>0$ and $N$? (The statement is indeed correct, but you should be able to justify it by finding a good pair of $c$ and $N$.)

Additional remark: when $f(n)$ is a polynomial of $n$, like for example $f(n)=n^{2}+1000n$, then the complexity is determined/dominated by the highest degree term. In this example, the highest degree term is $n^{2}$, and hence $f(n) = O(n^{2})$. But again, more general observation originates from the fact that we are able to find appropriate $c>0$ and $N$ and apply the definition.

| cite | improve this answer | |

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