Question

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 \Omega(g)$
• C. $f \in o(g)$
• D. $f \in \Theta(g)$

Hint:

Remember: If $f(n)$ grows slower than $g(n)$, then $f \in O(g)$ and also $f \in o(g)$, but not $\Omega(g)$ or $\Theta(g)$.

Answer 1

The Correct Option is A

To determine which of the given statements about the functions \(f(n) = n\) and \(g(n) = n^2\) are true, we need to analyze each option using the definitions of Big O, Omega, Little o, and Theta notation.

**1. Analysis of \(f \in O(g)\):**

• By definition, \(f \in O(g)\) means there exist positive constants \(c\) and \(n_0\) such that \(f(n) \leq c \cdot g(n)\) for all \(n \geq n_0\).
• Substitute the given functions: \(n \leq c \cdot n^2\).
• Rewriting gives: \(\frac{1}{c} \leq n\).
• This inequality will hold for any \(n \geq \frac{1}{c}\). For example, choosing \(c = 1\) and \(n_0 = 1\) suffices to satisfy this condition.
• Hence, \(f \in O(g)\) is true.

**2. Analysis of \(f \in \Omega(g)\):**

• By definition, \(f \in \Omega(g)\) means there exist positive constants \(c\) and \(n_0\) such that \(f(n) \geq c \cdot g(n)\) for all \(n \geq n_0\).
• Substitute the given functions: \(n \geq c \cdot n^2\).
• Rewriting gives: \(1 \geq c \cdot n\), which is not true for all large \(n\) because \(n^2\) grows faster than \(n\).
• Hence, \(f \in \Omega(g)\) is false.

**3. Analysis of \(f \in o(g)\):**

• By definition, \(f \in o(g)\) means that, for every positive constant \(\epsilon\), there exists a positive integer \(n_0\) such that \(f(n) < \epsilon \cdot g(n)\) for all \(n \geq n_0\).
• Substitute the given functions: \(n < \epsilon \cdot n^2\).
• Rewriting gives: \(\frac{1}{\epsilon} < n\), which is true for any \(n > \frac{1}{\epsilon}\).
• Hence, \(f \in o(g)\) is true because, as \(n\) grows larger, \(n^2\) indeed dominates \(n\) in growth.

**4. Analysis of \(f \in \Theta(g)\):** 

• By definition, \(f \in \Theta(g)\) means that there exist positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)\) for all \(n \geq n_0\).
• Substitute the given functions: \(c_1 \cdot n^2 \leq n \leq c_2 \cdot n^2\).
• This inequality cannot hold for large \(n\) because \(n\not\in\Theta(n^2)\).
• Hence, \(f \notin \Theta(g)\).

From the analysis, we conclude that the true statement is \(f \in O(g)\).