I have to prove this inequality using the complexity classes.

Question

I know that little-o is < or = to big-O. Θ(n log n) ∪ o(n log n) = O(n log n)

Answer 1

To prove the $\subseteq$ direction, you need to show two things.

• $\Theta(n \log n) \subseteq O(n \log n)$.
• $o(n \log n) \subseteq O(n \log n)$

Both are fairly straightforward to verify; just write down the definitions of $o()$, $\Theta()$, and $O()$.

---

I don't believe the $\supseteq$ direction holds. A counterexample is $$f(n) = \begin{cases} n \log n & \text{if $n$ even} \\ 0 & \text{if $n$ odd}\end{cases}$$ For this counterexapmle, the sequence $\frac{f(n)}{n \log n}$ is $1,0,1,0,1,0,\ldots$.

• It is clearly bounded from above by $1$, so it is in $O(n \log n)$.
• It is not in $o(n \log n)$ because this sequence does not converge to zero.
• It is not in $\Omega(n \log n)$ because this sequence is not bounded from below by a positive constant. Consequently it is not in $\Theta(n \log n)$ either.