GATE CS 1994 Q1.23 — Asymptotic Worst Case Time and Space Complexity

To determine the correct options, we analyze the asymptotic behavior of the functions $g_1(n)$ and $g_2(n)$ as $n \to \infty$. Asymptotic notations like Big-O ($O$) describe the behavior of functions for sufficiently large values of $n$.

For large values of $n$:

• For $n > 10,000$, the function $g_1(n) = n^2$. Thus, $g_1(n) = \Theta(n^2)$.
• For $n > 100$, the function $g_2(n) = n^3$. Thus, $g_2(n) = \Theta(n^3)$.

Now, let's evaluate each option:

1. $g_1(n) \text{ is } O(g_2(n))$: This translates to checking if $n^2 = O(n^3)$. Since $n^2 \le c \cdot n^3$ for all $n \ge 1$ (with $c=1$), this is True.
2. $g_1(n) \text{ is } O(n^3)$: This translates to checking if $n^2 = O(n^3)$, which is True.
3. $g_2(n) \text{ is } O(g_1(n))$: This translates to checking if $n^3 = O(n^2)$. Since $n^3$ grows strictly faster than $n^2$, this is False.
4. $g_2(n) \text{ is } O(n)$: This translates to checking if $n^3 = O(n)$, which is False.

Thus, the correct options are A and B.