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?

We are given the functions $f(n) = n$ and $g(n) = n^2$ for $n \in \mathbb{N}$.

To determine the asymptotic relations, consider the limit of their ratio as $n \to \infty$:

• Option A ($f \in O(g)$): $f(n) \in O(g(n))$ means that $f(n) \le c \cdot g(n)$ for some constant $c > 0$ and all sufficiently large $n$. Since $n \le n^2$ for all $n \ge 1$, this holds (with $c = 1$). Thus, (A) is TRUE.

• Option B ($f \in \Omega(g)$): $f(n) \in \Omega(g(n))$ requires that $f(n) \ge c \cdot g(n)$ for some constant $c > 0$ and all sufficiently large $n$. Since $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, $f(n)$ grows strictly slower than $g(n)$, so this does not hold. Thus, (B) is FALSE.

• Option C ($f \in o(g)$): $f(n) \in o(g(n))$ (little-o notation) is defined by $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$. Since this limit evaluates to $0$, (C) is TRUE.

• Option D ($f \in \Theta(g)$): $f(n) \in \Theta(g(n))$ requires both $f \in O(g)$ and $f \in \Omega(g)$. Since $f \notin \Omega(g)$, (D) is FALSE.

Hence, the correct statements are A and C.