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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ The zero function is in $O(n^{1/2})$, but not in $\Omega(n^{\sin(n)})$. $\endgroup$ – plop Mar 1 at 16:24
-
1$\begingroup$ Both $\sqrt{n} \leqslant n^{\sin n}$ and $n^{\sin n} \leqslant \sqrt{n}$ are asymptotically wrong. $\endgroup$ – zkutch Mar 1 at 16:58
Add a comment
|
$\begingroup$
$\endgroup$
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})$.
answered Mar 1 at 20:22
