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

We are given:
$f(n) = n$, $g(n) = n^2$.
Step 1: Check $f \in O(g)$.
We ask if $f(n) \leq c g(n)$ for some constant $c>0$ and sufficiently large $n$.
That is, $n \leq c n^2$.
For $n \geq 1/c$, this inequality holds true.
Hence, $f \in O(g)$ is True.
Step 2: Check $f \in \Omega(g)$.
We ask if $f(n) \geq c g(n)$ for some $c>0$ and sufficiently large $n$.
That is, $n \geq c n^2 \Rightarrow 1 \geq c n$.
This cannot hold for large $n$.
Hence, $f \in \Omega(g)$ is False.
Step 3: Check $f \in o(g)$.
We check the limit: $\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$.
Since the limit is $0$, $f \in o(g)$ is True.
Step 4: Check $f \in \Theta(g)$.
For $\Theta$, $f(n)$ must be both $O(g)$ and $\Omega(g)$.
We have $f \in O(g)$ but not in $\Omega(g)$.
Hence, $f \notin \Theta(g)$. False.
\[ \boxed{\text{True Statements: (A) and (C)}} \]