Statement II: f(n) = O(g(n)) ⇒ Ig(f(n)) = O(1g(g(n))) where Ig(g(n)) ≥1 for all sufficient large n.
In the light of the above statements, choose the most appropriate answer from the options given below.
1.Both Statement I and Statement II are correct ✓ Correct
2.Both Statement I and Statement II are incorrect
3.Statement I is correct but Statement II is incorrect
4.Statement I is incorrect but Statement II is correct
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)).
