GATE CS 2023 Q19 — Asymptotic Worst Case Time and Space Complexity

We are given two functions of natural numbers:

$$f(n) = n \quad \text{and} \quad g(n) = n^2$$

Let us analyze each asymptotic relation between $f(n)$ and $g(n)$:

1. Big-O notation ($O$):

   $f(n) \in O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

   Since $n \le 1 \cdot n^2$ for all $n \ge 1$, this condition holds. Thus, $f \in O(g)$ is TRUE (Option A).

2. Big-Omega notation ($\Omega$):

   $f(n) \in \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \ge c \cdot g(n)$ for all $n \ge n_0$.

   Since $n$ grows strictly slower than $n^2$, we cannot find such a constant $c > 0$ for large $n$. Thus, $f \in \Omega(g)$ is FALSE (Option B).

3. Little-o notation ($o$):

   $f(n) \in o(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

   Evaluating the limit:

   $$\lim_{n \to \infty} \frac{n}{n^2} = \lim_{n \to \infty} \frac{1}{n} = 0$$

   Thus, $f \in o(g)$ is TRUE (Option C).

4. Theta notation ($\Theta$):

   $f(n) \in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Since $f(n) \notin \Omega(g(n))$, $f \in \Theta(g)$ is FALSE (Option D).