Solution

The correct answer is Both Statement I and Statement II are correct

Key PointsIn the asymptotic analysis, we refer to Big O notation (O) and Big Omega notation (Ω) to describe upper and lower bounds of functions respectively.

• Statement I is asserting that if f(n) ≥ 1 and f(n) is upper-bounded by g(n) (f(n) = O(g(n))), then g(n) should be lower-bounded by f(n) (g(n) = Ω(f(n))). In other words, if f(n) grows no faster than g(n), then g(n) grows at least as quickly as f(n). This statement is correct.
• Statement II, If f(n) = O(g(n)), then a function Ig(f(n)), which is presumably larger or equal to 1 for all sufficiently large n, would be bound by O(1g(g(n))). This seems to depend on the specific nature of the functions f(n) and g(n). This statement is correct.

Additional Information

• Reflexivity: f(n) = (f(n)). Valid for O and 2.
• Transitivity: f(n) = (g(n)) and g(n) = (h(n)) = f(n) = (h(n)). Valid for O and Ω as well.
• Symmetry: f(n) = (g(n)) if and only if g(n) = (f(n)).
• Transpose symmetry: f(n) = O(g(n)) if and only if g(n) = (f(n)).
• If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)).
• If f₁(n) is in O(g₁(n)) and f₂(n) is in O(92(n)), then (f₁ + f2)(n) is in O(max(9₁(n)), (g₁(n))).
• If f₁(n) is in O(g₁(n)) and f₂(n) is in O(g₂(n)) then f₁(n) f₂(n) is in O(g₁(n) g₁(n)).