# Is $𝑂(𝑛^{1/2}) = \Omega(𝑛^{\sin(n)})$?

As $$-1 <\sin(n) < 1$$, So $$n^{\sin(n)}$$ is bounded, but square root of $$n$$ tends to infinity. Is my logic correct? But from the other perspective, $$1/n \leq n^{\sin(n)} \leq n$$. I am confused.

• The zero function is in $O(n^{1/2})$, but not in $\Omega(n^{\sin(n)})$. – plop Mar 1 at 16:24
• Both $\sqrt{n} \leqslant n^{\sin n}$ and $n^{\sin n} \leqslant \sqrt{n}$ are asymptotically wrong. – zkutch Mar 1 at 16:58

First, let's unpack this. We say that $$O(\sqrt{n}) = \Omega(n^{\sin n})$$ if any function $$f(n)$$ which satisfies $$f(n) = O(\sqrt{n})$$ also satisfies $$f(n) = \Omega(n^{\sin n})$$. In particular, if $$O(\sqrt{n}) = \Omega(n^{\sin n})$$ then $$\sqrt{n} = \Omega(n^{\sin n})$$. If $$\sqrt{n} = \Omega(n^{\sin n})$$ then according to the definition, there exist $$C,N>0$$ such that $$\sqrt{n} \geq Cn^{\sin n}$$ for all $$n \geq N$$. Let us assume that this is the case.
In what follows, I assume that the argument in $$\sin n$$ is measured in radians.
Since $$2\pi$$ is irrational, the sequence $$n \bmod 2\pi$$ is equidistributed in $$[0,2\pi)$$. In particular, there are infinitely many $$n$$ such that $$n \bmod 2\pi \in (0.4\pi,0.6\pi)$$, and so $$\sin n \geq 0.95$$. For each such $$n \geq N$$, we have $$\sqrt{n} \geq Cn^{\sin n} \geq Cn^{0.95} \Longrightarrow n \leq C^{1/0.45}.$$ Since there are infinitely many $$n$$ such that $$\sin n \geq 0.95$$, we can find one such $$n$$ which exceeds both $$N$$ and $$C^{1/0.45}$$, and so reach a contradiction. This shows that $$\sqrt{n}$$ is not $$\Omega(n^{\sin n})$$.