Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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. – Stella Biderman Mar 23 '14 at 3:58
up vote 9 down vote accepted

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|cite|improve this answer
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})$.

share|cite|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! – 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)$.

share|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.