Take the 2-minute tour ×
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.

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
2  
No, there isn't –  Karolis Juodelė Mar 22 at 17:29
1  
Out of sheer curiosity, might I ask what algorithm has the effed up complexity class $O(n^\sin(n))$? –  Christian Mar 23 at 1:31
    
^^ Seconded. Unless this was just out of curiosity which seems likely. –  Joshua Biderman Mar 23 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 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 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 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 at 18:02
    
OHH now I understood, that was pretty helpful. Thanks a lot! –  user137227 Mar 22 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 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 at 18:33

Your Answer

 
discard

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.