GATE CSE 2023 Q29: Asymptotic relations between f(n) = n and g(n) = n²

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?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, C (official GATE 2023 final answer key)

Concept used: Definitions of $O$ , $\Omega$ , $\Theta$ and little- $o$ via the limit of $f(n)/g(n)$ .

First step: Compute $\lim_{n \to \infty} \frac{n}{n^2} = 0$ and read off which relations hold.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key