GATE CS 2022 Q1 — Asymptotic Worst Case Time and Space Complexity

Let us analyze each option to determine the correct statement:

• Option A: Let $f(n)$ be a polynomial of degree $k$ where $k \ge 0$. Then, $f(n) = \Theta(n^k)$.
  • $f(n^2) = \Theta((n^2)^k) = \Theta(n^{2k})$
  • $(f(n))^2 = \Theta((n^k)^2) = \Theta(n^{2k})$
  Since both expressions are asymptotically equivalent to $n^{2k}$, we have $f(n^2) = \Theta((f(n))^2)$. Thus, Option A is TRUE.
• Option B: Let $f(n) = n$. Then $f(n^2) = n^2$ and $(f(n))^2 = n^2$. Since $n^2 = \Theta(n^2)$, it is not $o(n^2)$. Thus, Option B is false.
• Option C: Let $f(n) = 2^n$ (an exponential function). Then $f(n^2) = 2^{n^2}$ and $(f(n))^2 = 2^{2n}$. Since $2^{n^2}$ grows much faster than $2^{2n}$, $f(n^2) \neq O((f(n))^2)$. Thus, Option C is false.
• Option D: Let $f(n) = 2^{-n}$ (a positive decreasing function). Then $f(n^2) = 2^{-n^2}$ and $(f(n))^2 = 2^{-2n}$. For large $n$, $2^{-n^2} < 2^{-2n}$, so $f(n^2) \neq \Omega((f(n))^2)$. Thus, Option D is false.