Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^\frac{1+\sin(\frac{n\pi}{2})}{2}$ and $g(n) = \sqrt{n}$.

Question

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^{\big(\displaystyle 1+\sin({n\pi}/{2})\big)/2}$ and $g(n) = \sqrt{n}$.

I tried plotting this out - it oscillates, and the exponential is $0 \le x \le 1$... so I have no idea how to prove it using inequalities and what not.

Help appreciated!

Answer 1

Neither $O(), \Omega()$ nor $\Theta()$ holds. Clue for proof: for $n=4k+1,\space sin(\frac{n\pi}{2})=1$ and then $f(n) = n$. That last argument is sufficient to show that $f(n)\neq O(g(n))$. A similiar argument($n=4k+3$) will yield $f(n)\neq \Omega(g(n))$ which will evidently lead also to $f(n)\neq \Theta(g(n))$.