Growth rate of $n^{\sin n}$

Question

Is there a way of comparing the growth of functions $ f(n) = n ^ {\sin(n)} $ and $ g(n) = n ^ {1/2} $ in terms of $ O, o, \Omega, \omega, \Theta $ ?

Periodically, $ f(n) $ keeps going above and below $ g(n) $ and I couldn't think in any multiplicative constant which may help here. Any thoughts?

Thanks in advance!

Answer 1

Neither of these functions are $O$ or $\Omega$ of the other, since neither $f(n)/g(n)$ nor $g(n)/f(n)$ is bounded.

In other words, they are not asymptotically comparable.

Answer 2

There are infinitely many integers $n$ such that $\sin n\gt\frac{\sqrt{3}}{2}\gt \frac{1}{2}$.

For note that $n+1$ differs from $n$ by $1$ radian, a bit under $60$ degrees. Thus infinitely many $n$ fall between $2\pi k+\frac{\pi}{3}$ and $2\pi k+\frac{2\pi}{3}$, where $k$ ranges over the positive integers. In that interval, the sine function is greater than $\frac{\sqrt{3}}{2}$.

Added: The above shows that for any positive constant $c$, there are (infinitely many) $n$ such that $n^{\sin n}\gt cn^{1/2}$.

This is because for infinitely many $n$, we have $\frac{f(n)}{g(n)}\gt n^{(1/2)(\sqrt{3}-1)}$.

Thus $n^{\sin n}$ is not $O(n^{1/2})$.

The other direction is easy, $n^{\sin n}\lt 1$ for infinitely many $n$, so $n^{1/2}$ is not $O(n^{\sin n})$.

Answer 3

$f(n)=O(n)$, because $|f(n)| \le 1\cdot|n|$ for all $n$.

$g(n)=O(\sqrt n)$, because $|g(n)| \le 1\cdot|\sqrt n|$ for all $n$.

$f(n)\ne O(\sqrt n)$, because for any $M$ there is at least one $n$ such that $|n^{\sin n}| > M|\sqrt n|$.

In other words, $f(n)$ has a higher growth rate than $g(n)$.