Let f(n) and g(n) be asymptotically positive functions. Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)). Statement II: f(n) = O(g(n)) ⇒ lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n. Choose the most appropriate answer.

1. ABoth Statement I and Statement II are correct
2. BBoth Statement I and Statement II are incorrect
3. CStatement I is correct but Statement II is incorrect
4. DStatement I is incorrect but Statement II is correct

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. Both Statement I and Statement II are correct

Explanation

I is the transpose symmetry of O and Ω. For II, f ≤ c·g gives lg f ≤ lg c + lg g ≤ (lg c + 1)·lg g once lg g ≥ 1, so lg f = O(lg g). Both hold (CLRS Problem 3-4).