Let f(n), g(n) and h(n) be functions defined for positive integers such that f(n) = Omega(g(n)), g(n) = Omega(h(n)), g(n) != O(f(n)), and h(n) != O(f(n)). Which one of the following statements is FALSE? A. f(n) = Omega(h(n)) B. h(n) = O(f(n)) C. f(n) != O(g(n)) D. f(n)(h(n)) != O(g(n)(h(n)))

GATE 2004 · Algorithms · Asymptotic Notations · medium

Answer: Statement B (h(n) = O(f(n))) is FALSE because the problem explicitly states h(n) != O(f(n)).

1. Check option A: f(n) = Omega(h(n)): Since f = Omega(g) and g = Omega(h), by transitivity of Omega, f = Omega(h). Statement A is TRUE.
2. Check option B: h(n) = O(f(n)): The problem explicitly states h(n) != O(f(n)). Statement B directly contradicts this given condition, so B is FALSE.
3. Verify options C and D are true: C: f != O(g) follows because if f = O(g) and f = Omega(g) then f = Theta(g) which would mean g = O(f), contradicting g != O(f). So C is TRUE. D: Since f is not O(g), multiplying both sides by h preserves the strict ordering, so f*h != O(g*h). D is TRUE.