GATE 2023 CS – Question 29

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple select

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?

$f \in O(g)$
$f \in \Omega(g)$
$f \in o(g)$
$f \in \Theta(g)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $f \in O(g)$; (C) $f \in o(g)$

Explanation

n grows strictly slower than n², since n/n² → 0. So f ∈ O(g) and f ∈ o(g), while f ∉ Ω(g) and f ∉ Θ(g).