Which of the following is the CORRECT for O- notation?
2023
Which of the following is the CORRECT for O- notation?
- A.
O (g (n)) = {f (n): there exist positive constant C and n₀ such that 0 ≤ f (n) ≤ cg (n) for all n ≥ n₀}
- B.
O (g (n)) = {f (n): there exist positive constant C and n₀ such that 0 ≤ C g (n) ≤ f (n) for all n ≥ n₀}
- C.
O (g (n)) = {f (n): there exist positive constant C₁, C₂ and n₀ such that 0 ≤ C₁ g (n) ≤ f (n) ≤ C₂ g (n) for all n ≥ n₀}
- D.
O (g (n)) = {f (n): there exist positive constant C and n₀ such that 0 ≥ f (n) ≥ cg (n) for all n ≥ n₀}
Attempted by 140 students.
Show answer & explanation
Correct answer: A
Big-O notation defines an upper bound: f(n) is O(g(n)) if there are positive constants C and n0 such that 0 <= f(n) <= Cg(n) for all n >= n0.