GATE 2022 CS Q.11: solution and answer

Official answer: ASource: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. Restrict attention to the class named in each option, then either prove the Θ/O/o/Ω relation holds for every function in that class, or find one positive function in that class for which it fails.

2. Option (A): let f(n) be any polynomial of degree k with positive leading coefficient c (forced positive since f(n)>0 for large n). Then f(n) = c·n^k + lower-order terms, so f(n) = Θ(n^k) — the lower-degree terms are dominated by the leading term for large n, regardless of how many terms f has.

3. Substitute n → n²: f(n²) = Θ((n²)^k) = Θ(n^{2k}).

4. Square the relation f(n) = Θ(n^k): if c₁n^k ≤ f(n) ≤ c₂n^k eventually, then c₁²n^{2k} ≤ f(n)² ≤ c₂²n^{2k} eventually, so f(n)² = Θ(n^{2k}) as well.

5. Since f(n²) and f(n)² are both Θ(n^{2k}), and Θ is a transitive equivalence relation, f(n²) = Θ(f(n)²) holds for every polynomial f(n) — option (A) is TRUE in general.

6. Option (B): counterexample f(n) = n. f(n²) = n², f(n)² = n². The two are equal (ratio → 1), so f(n²) is not o(f(n)²) — (B) is false.

7. Option (C): counterexample f(n) = 2^n (exponential). f(n²) = 2^{n²}, f(n)² = 2^{2n}. Since n² − 2n → ∞, the ratio 2^{n²}/2^{2n} → ∞, so f(n²) is NOT O(f(n)²) — (C) is false.

8. Option (D): counterexample f(n) = log n. f(n²) = 2 log n, f(n)² = (log n)². The ratio f(n²)/f(n)² = 2/log n → 0, so f(n²) = o(f(n)²), meaning it CANNOT also be Ω(f(n)²) — (D) is false.

9. Only (A) survives as universally true for its stated class of functions.