2

Can a function belong to two different big Os if the latter is bigger? for example:

$n \in O(n) $ and $n \in O(n^2)$ for $O(n^2) \ge O(n)$

I guess this is not always true, but for the above case it would work as by definition we can have $n=C=1 or 0$ would make them equal and other cases would be smaller, right?

$n \le Cn^2 \rightarrow 1\le 1 $

How do you prove something is not big Os of something? for example: show $n\not \in O(nlogn) $

glockm15
  • 587
  • 1
    You would be right in the case of "little-o" ("$o$"), but in the case of "big-o" ("$O$"), we cannot have both $f(n)\in O(n)$ and $f(n)\in O(n^2)$ – Peter May 31 '18 at 13:35

1 Answers1

1

$f(x) \in O(g(x)) \Leftrightarrow \lim_{x\rightarrow\inf}\frac{f(x)}{g(x)}$ is finite and non-zero.

$n$ is not in $O(n^2)$, $O(n^2) \gt O(n)$.

peterh
  • 2,683