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

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?

-
No, there isn't – Karolis Juodelė Mar 22 '14 at 17:29
Out of sheer curiosity, might I ask what algorithm has the effed up complexity class $O(n^\sin(n))$? – Christian Mar 23 '14 at 1:31
^^ Seconded. Unless this was just out of curiosity which seems likely. – Stella Biderman Mar 23 '14 at 3:58

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.

-
That makes sense. Thanks a lot! – gcolucci Mar 22 '14 at 17:45

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})$.

-
I think the issue is that if I keep growing the values of n, after $5\pi/6$, the $g(n)$ function is above $f(n)$ and therefore an asymptotical analysis couldn't be made just by this. But thanks for your help! – gcolucci Mar 22 '14 at 17:44
But in order to define the $O$ analysis, we must think in a constant $c$ and a $n_0$, which makes $n ^ {sin n}$ always greater than $n ^ {1/2}$ for all $n > n_0$. In fact, we have infinite n that accomplish this, but not all n in the asymptotical limit. Doesn't this invalidate the analysis? – gcolucci Mar 22 '14 at 17:57
It does not invalidate the analsis. We have shown that $n^{\sin n}$ is not $O(n^{1/2})$, and also that the big-Oh relation does not hold the other way either. – André Nicolas Mar 22 '14 at 18:02
OHH now I understood, that was pretty helpful. Thanks a lot! – gcolucci Mar 22 '14 at 18:08
You are welcome. The no $c$ will work comes from the fact that the exponent $(1/2)(\sqrt{3}-1)$ in the added material is positive. – André Nicolas Mar 22 '14 at 18:10

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

-
According to that reasoning $f$ also has a lower growth rate than $g$, because $g\in\Omega(1)$ but $f\notin\Omega(1)$. – Henning Makholm Mar 22 '14 at 18:33