0

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!

Caleb Stanford
  • 45,895
Gabba
  • 1
  • 2
    You should show us some work. A proof/disproof for $f(n) = O(g(n))$ is the evaluation of a certain limsup. Which one? Can you evaluate it? There are similar questions for you concerning the other two questions. – GEdgar Mar 08 '14 at 14:31

1 Answers1

0

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

user3054303
  • 158