-1

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

Julian
  • 11

1 Answers1

0

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.
angryavian
  • 89,882