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

Question

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

Answer 1

Consider the sequence

$$a_n=\begin{cases} n\log n & \text{if } n \text{ is even} \\ 0 & \text{if }n \text{ is odd} \end{cases}$$

This sequence is in $O(n\log n)$ because

$$a_n \le n\log n\quad \forall n$$

but not in $\Theta(n\log n)\cup o(n\log n)$, because

• it is not in $o(n\log n)$ because for $k=0.5$, $\nexists n_0$ such that $a_n < k \cdot n\log n \quad \forall n\ge n_0$.

• it is not in $\Theta(n\log n)$ because $\nexists k_1>0, n_0>0$ such that $a_n \ge k_1\cdot n\log n\quad \forall n\ge n_0$.

Therefore, the two sets are not equal.

Answer 2

$\newcommand{gae}[1]{\newcommand{#1}{\operatorname{#1}}}\newcommand{abs}[1]{\left\lvert{#1}\right\rvert}$A fair idea is that $\cos^2\left(\frac n2\pi\right)n\log n$ is frequently $0$, and frequently $n\log n$, therefore it can neither be in $o(n\log n)$ nor in $\Theta(n\log n)$, while still being in $O(n\log n)$.

However, if you want positive and increasing functions, you can devise such an element of $O(n\log n)\setminus(\Theta(n\log n)\cup o(n\log n))$ as follows.

Call $L(n)=n\log n$. Notice that, for all $N\in\Bbb N$, for all $\varepsilon >0$ and for all $x\in\Bbb R$ there is some natural number $M>N$ such that $\abs{\frac{x}{L(n-1)}}<\varepsilon$ for all $n\ge M$. We may, for the sake of constructibility, call $M(N,\varepsilon, x)$ the least such $M$. Now, it is possible to devise a strictly increasing sequence $\{a_m\}_{m\in\Bbb N}$ such that $\abs{\frac{L(a_m)}{L(a_{m+1}-1)}}<2^{-m}$ for all $m\in\Bbb N$. A technical way to do so would be with the recursion $$\begin{cases} a_0=1\\ a_{m+1}=M(a_m,L(a_m),2^{-m})\end{cases}$$

Once we have such a sequence $\{a_m\}_{m\in\Bbb N}$ at hand, we may define a weakly increasing positive function $F:\Bbb N\to\Bbb R$ such that $\limsup_{n\to\infty} \frac{F(n)}{L(n)}=1$ and $\liminf_{n\to\infty} \frac{F(n)}{L(n)}=0$ quite handily. The function will be definned by the property of having $F(n)=L(a_m)$ for all $n$ such that $a_m\le n< a_{m+1}$. Since $L(a_m)< L(a_{m+1})$, $F$ is a weakly increasing "piecewise constant" function. $\frac{F(a_m)}{L(a_m)}$ is $1$ for all $m$, and it the decreases to less than $2^{-m}$ for all $n$ between $a_m$ and $a_{m+1}-1$ (notice in fact that the "last" one is $\frac{L(a_m)}{L(a_{m+1}-1)}<2^{-m}$ ).

Since everything is positive and $F(n)\le L(n)$ by monotonicity of $L$, indeed $0=\liminf_{n\to\infty} \frac{F(n)}{L(n)}<\limsup_{n\to\infty} \frac{F(n)}{L(n)}=1$.

You might have noticed that the same procedure can be repeated whenever $L(n)$ is an increasing (positive) sequence which diverges to $\infty$.

If you want $F$ to be strictly increasing as well, you may consider something like $\widetilde F(n)=F(n)+1-2^{-n}$.