Let f and g be functions of natural numbers given by \(f(n)\) = n and \(g(n)\)…
2023
Let f and g be functions of natural numbers given by \(f(n)\) = n and \(g(n)\) = n2. Which of the following statements is/are TRUE?
- A.
\(f ∈ O(g)\) - B.
\(f ∈ Ω(g)\) - C.
\(f ∈ o(g)\) - D.
\(f ∈ Θ(g)\)
Attempted by 345 students.
Show answer & explanation
Correct answer: A, C
Answer: f(n)=n is O(g(n)=n^2) and is also o(g(n)=n^2); f(n)=n is not Ω(g(n)=n^2) and therefore not Θ(g(n)=n^2).
f(n)=n ∈ O(g(n)=n^2): For n≥1 we have n ≤ n^2, so choosing c=1 and n0=1 gives f(n) ≤ c·g(n) for all n≥n0.
f(n)=n ∈ o(g(n)=n^2): f(n)/g(n) = 1/n → 0 as n → ∞, which is the definition of little-o.
f(n)=n ∉ Ω(g(n)=n^2): Ω would require n ≥ c·n^2 for some c>0 and large n, which fails; equivalently f(n)/g(n) does not stay above a positive constant.
f(n)=n ∉ Θ(g(n)=n^2): Θ requires both O and Ω; since Ω fails, Θ cannot hold.