GATE 2023 CS Q.29: solution and answer

GATE 2023 · CSQ.29 · 1 mark · MSQ

Let $f$ and $g$ be functions of natural numbers given by $f (n) = n$ and $g (n) = n^{2}$ . Which of the following statements is/are TRUE?

(A)
$f \in O (g)$
(B)
$f \in Ω (g)$
(C)
$f \in o (g)$
(D)
$f \in Θ (g)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

A and C are TRUE.

Official answer: A, CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

Definitions recap. For $f (n) = n$ and $g (n) = n^{2}$ : $f \in O (g)$ means $f (n) \leq c \cdot g (n)$ for some constant $c > 0$ and all sufficiently large $n$ ; $f \in Ω (g)$ means $f (n) \geq c \cdot g (n)$ for some constant $c > 0$ and all sufficiently large $n$ ; $f \in o (g)$ means $lim_{n \to \infty} \frac{f ( n )}{g ( n )} = 0$ ; $f \in Θ (g)$ means both $O (g)$ and $Ω (g)$ hold.
Option A — $f \in O (g)$ : Taking $c = 1$ , $n \leq n^{2}$ for every $n \geq 1$ . So $f (n) \leq c \cdot g (n)$ holds for all $n \geq 1$ . TRUE.
Option B — $f \in Ω (g)$ : This would require $n \geq c \cdot n^{2}$ for some fixed constant $c > 0$ and all large $n$ , i.e. $c \leq \frac{1}{n}$ . But $\frac{1}{n} \to 0$ as $n \to \infty$ , so no single positive constant $c$ can satisfy this for all sufficiently large $n$ . FALSE.
Option C — $f \in o (g)$ : $n \to \infty lim \frac{f ( n )}{g ( n )} = n \to \infty lim \frac{n}{n ^{2}} = n \to \infty lim \frac{1}{n} = 0$ . TRUE.
Option D — $f \in Θ (g)$ : $Θ (g)$ requires both $O (g)$ AND $Ω (g)$ to hold. Since $Ω (g)$ was shown FALSE in Option B, $Θ (g)$ cannot hold. FALSE.
Conclusion: The TRUE statements are A and C.

KEY IDEA

Compare growth rates of $f (n) = n$ and $g (n) = n^{2}$ using the formal definitions of $O$ , $Ω$ , $o$ , and $Θ$ : since $n$ grows strictly slower than $n^{2}$ , $f$ is an upper-bounded-by (in fact strictly dominated, i.e. little-o) function of $g$ , but not a lower bound, so $Ω$ and $Θ$ fail.

WATCH OUT FOR

Assuming that because $f \in O (g)$ holds, $f \in Θ (g)$ must also hold (treating $O$ as if it already implied a tight bound), or forgetting that $o (g)$ (strict, limit-zero domination) is a stronger and still-true statement here, not something mutually exclusive with $O (g)$ .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2023 CS Q.29: solution and answer

Answer and solution

More Complexity questions