GATE CS 2015 Set 3 Q42 — Asymptotic Worst Case Time and Space Complexity

To determine the relationship between $f(n) = n$ and $g(n) = n^{1 + \sin n}$, we analyze the ratio $\frac{f(n)}{g(n)}$ as $n \to \infty$.

The term $\sin n$ oscillates densely in the interval $[-1, 1]$ as $n$ ranges over the positive integers. Let us compute the ratio:

Now, let's evaluate both statements:

1. Statement I: $f(n) = O(g(n))$

   For $f(n) = O(g(n))$ to hold, there must exist a positive constant $c$ such that $\frac{f(n)}{g(n)} \le c$ for all sufficiently large $n$.

   However, we can choose a sequence of integers $n$ where $\sin n \approx -1$. For these values:

   $$\frac{f(n)}{g(n)} = n^{-\sin n} \approx n^1 = n$$

   As $n \to \infty$, this ratio grows without bound. Thus, no such constant $c$ exists, and $f(n) \neq O(g(n))$. Statement I is incorrect.

2. Statement II: $f(n) = \Omega(g(n))$

   For $f(n) = \Omega(g(n))$ to hold, there must exist a positive constant $c > 0$ such that $\frac{f(n)}{g(n)} \ge c$ for all sufficiently large $n$.

   However, we can choose a sequence of integers $n$ where $\sin n \approx 1$. For these values:

   $$\frac{f(n)}{g(n)} = n^{-\sin n} \approx n^{-1} = \frac{1}{n}$$

   As $n \to \infty$, this ratio approaches $0$. Thus, the ratio cannot be bounded below by any positive constant $c > 0$. Therefore, $f(n) \neq \Omega(g(n))$. Statement II is incorrect.

Since both statements are incorrect, the correct option is D.