# Show that the union of Θ and o is not O

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

• "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. – j_random_hacker Nov 9 '19 at 11:59
• 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 – Matthew C Nov 9 '19 at 22:15

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))$$.
• 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)$. – Daniel Nov 9 '19 at 22:10