1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Where you find such inequalities? $\endgroup$
    – zkutch
    Sep 17, 2020 at 11:00
  • $\begingroup$ @zkutch, what do you mean by "inequalities" ? $\endgroup$
    – John Smith
    Sep 17, 2020 at 11:02
  • $\begingroup$ I want to understand what: > 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$
    – John Smith
    Sep 17, 2020 at 11:05

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Can you elaborate? I've seen this before, but, wasn't so sure. Thanks. $\endgroup$
    – John Smith
    Sep 17, 2020 at 13:23
  • $\begingroup$ @JohnSmith Please see the new included example. $\endgroup$
    – OmG
    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$
    – John Smith
    Sep 17, 2020 at 17:09
  • $\begingroup$ So, what does this statement mean: $$O(nlogn) < O(n^2)$$ ?? $\endgroup$
    – John Smith
    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$
    – OmG
    Sep 17, 2020 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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