What do the following mean, in the context of greater than, or smaller than?
$$ O(n \log n) > O(n) $$
$$ O(nlogn) < O(n^2) $$
$\begingroup$
$\endgroup$
3
1 Answer
$\begingroup$
$\endgroup$
5
In this context, this comparison means the subset of. Hence, $O(n\log n) > O(n)$ means All members of $O(n)$ exist in $O(n \log n)$ as well or $O(n) \subset O(n \log n)$. For example, $f(n) = \sqrt{n} \in O(n)$ and $f(n) \in O(n\log n) $ and $g(n) = n \log n \not \in O(n)$ and $g(n) \ \in O(n \log n)$.
-
$\begingroup$ Can you elaborate? I've seen this before, but, wasn't so sure. Thanks. $\endgroup$ Commented Sep 17, 2020 at 13:23
-
$\begingroup$ @JohnSmith Please see the new included example. $\endgroup$– OmGCommented Sep 17, 2020 at 13:28
-
$\begingroup$ So, if, Algorithm1 is $$O(n)$$, and we modify it so, that it includes $$O(NlogN)$$, then we can exclude $$O(n)$$, and then the new algorithm is more dominant thus: $$O(n \log n) > O(n)$$ $\endgroup$ Commented Sep 17, 2020 at 17:09
-
$\begingroup$ So, what does this statement mean: $$O(nlogn) < O(n^2)$$ ?? $\endgroup$ Commented Sep 17, 2020 at 17:11
-
$\begingroup$ @JohnSmith You can interpret $O(n\log n) < O(n^2)$ such as the other case. For example, $n \sqrt{n} \in O(n^2)$, but it is not in $O(n\log n)$. $\endgroup$– OmGCommented Sep 17, 2020 at 17:45
>or<between two Big-O notations for time complexity implies or means? Does it mean that the one that is greater is better, or the one that is less then is greater? $\endgroup$