Question 52

We are given $f(n) = n$ and $g(n) = n^{1 + \sin n}$ for positive integers $n$.

The function $\sin n$ oscillates continuously in the interval $[-1, 1]$ as $n \to \infty$:

• For values of $n$ where $\sin n \approx -1$, the exponent is $1 + \sin n \approx 0$, so $g(n) \approx n^0 = 1$. Here $\frac{f(n)}{g(n)} = \frac{n}{1} = n \to \infty$.
  Because $\frac{f(n)}{g(n)}$ is unbounded as $n \to \infty$, there is no constant $c$ such that $f(n) \le c \cdot g(n)$ for all large $n$. Thus, $f(n) \ne O(g(n))$, and Statement I is false.

• For values of $n$ where $\sin n \approx 1$, the exponent is $1 + \sin n \approx 2$, so $g(n) \approx n^2$. Here $\frac{g(n)}{f(n)} = \frac{n^2}{n} = n \to \infty$.
  Because $\frac{f(n)}{g(n)} \to 0$, there is no positive constant $c$ such that $f(n) \ge c \cdot g(n)$ for all large $n$. Thus, $f(n) \ne \Omega(g(n))$, and Statement II is false.

Because neither asymptotic relation holds, the answer is Neither I nor II (Option D).