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