Let f(n) and g(n) be asymptotically positive functions. The following…
2023
Let f(n) and g(n) be asymptotically positive functions. The following conjectures are given
In the light of the above statements, choose the most appropriate answer from the options given below
- A.
Both statement I and statement II are correct
- B.
Both statement I and statement II are incorrect
- C.
Both statement I is correct but statement II is incorrect
- D.
Both statement I is incorrect but statement II are correct
Attempted by 132 students.
Show answer & explanation
Correct answer: A
Statement I is true because f(n) = O(g(n)) implies f(n) ≤ c · g(n), which rearranges to g(n) ≥ (1/c)f(n), satisfying the definition of Ω(f(n)). Statement II is true because f(n) ≤ c · g(n) implies lg(f(n)) ≤ lg(c) + lg(g(n)). Since lg(g(n)) ≥ 1, the term lg(c) is bounded by a constant multiple of lg(g(n)), confirming lg(f(n)) = O(lg(g(n))). Both statements are valid.
A video solution is available for this question — log in and enroll to watch it.