2
$\begingroup$

Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$

I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would have to just show that $o(n \log n) \neq O(n \log n) $ Which would be easier I think. But I don't know how to go about this formally..

$\endgroup$
  • 1
    $\begingroup$ "intuitively isn't $\Theta \cup o=o$?" -- no, intuitively $\Theta(m)$ means "roughly equal to $m$" and $o(m)$ means "much less than $m$", so it's more intuitive to think of these as being disjoint. But in any case, intuition won't help you much here -- each of these three expressions is a set of functions (of $n$), and you need to work with the definitions of these sets. You need to find some function of $n$ that is in the LHS but not the RHS, or vice versa. $\endgroup$ – j_random_hacker Nov 9 '19 at 11:59
  • $\begingroup$ The definition of o means that in a sense, o(f(n)) is an “integral” full step smaller than f(n). I would try to find a function that satisfies f(n)/n or f(n)/log n or f(n)/(n log n)^0.5 goes to zero $\endgroup$ – Matthew C Nov 9 '19 at 22:15
4
$\begingroup$

An obvious function is $$ f(n) = \begin{cases} n \log n & \text{if $n$ is even}, \\ 0 & \text{if $n$ is odd}. \end{cases} $$

It's in $O (n \log n)$, it's not in $o (n \log n)$ and not in $\Theta(n \log n)$.

By the way: Every function in $\Theta(f(n)))$ is in $O(f(n))$, just take the larger constant from the $\Theta$ definition. And every function in $o(f(n))$ is also in $O(f(n))$, choose $c = 1$ and make $n$ large enough. But not the other way around.

$O(f(n))$ contains functions that have infinitely many values between $c_1 f(n)$ and $c_2 f(n)$, but also infinitely many small values. So a function $g(n) = f(n)$ for infinitely many $n$, and $g(n) = 0$ for infinitely many $n$ where $f(n) \ne 0$ is in $O (f(n))$, but not in $\Theta(f(n))$ and not in $o (f(n))$.

$\endgroup$
  • $\begingroup$ To add to that, the intuition that $\Theta \cup o = O$ holds for "well behaving functions". Consider the definition of the function classes using limits. If $\lim f(x)/g(x)$ exists, then $g \in O(f)$ if and only if $g \in \Theta(f) \cup o(f)$. $\endgroup$ – Daniel Nov 9 '19 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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