GATE CS 2023 Q.29: Asymptotic Analysis and Time/Space Complexity

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)$

Official answer and solution

Solution

Evaluate the asymptotic ratio $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ for $f(n) = n$ and $g(n) = n^2$ .

We compute the limit of the ratio as $n \to \infty$ :

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n}{n^2} = \lim_{n \to \infty} \frac{1}{n} = 0

Because the limit is finite ( $= 0$ ), $f(n) = O(g(n))$ , so statement (A) is TRUE.
Because the limit is strictly $0$ , $f(n) = o(g(n))$ (little-o), so statement (C) is TRUE.
Because the limit is $0$ , $f(n) \notin \Omega(g(n))$ and $f(n) \notin \Theta(g(n))$ . Statements (B) and (D) are FALSE.

Final answer

Options (A, C)

Common trap

Forgetting that $f(n) = o(g(n))$ automatically implies $f(n) = O(g(n))$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.