Take the 2-minute tour ×

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!

share|improve this question
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. –  Joshua Biderman Mar 23 '14 at 3:58

3 Answers 3

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.

share|improve this answer
That makes sense. Thanks a lot! –  user137227 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})$.

share|improve this answer
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! –  user137227 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? –  user137227 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! –  user137227 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)$.

share|improve this answer
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

Your Answer


