Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n)…

Given:

• f(n) = O(g(n))

• g(n) ≠ O(f(n)) (so g grows strictly faster than f in the asymptotic sense)

• g(n) = O(h(n)) and h(n) = O(g(n)) (so g and h are Theta of each other)

Consequences and reasoning:

• By transitivity of O(), from f(n) = O(g(n)) and g(n) = O(h(n)) we get f(n) = O(h(n)).

• Therefore f(n) + g(n) = O(g(n)) and since g(n) = O(h(n)), we have f(n) + g(n) = O(h(n)).

• Multiplying the inequality f(n) ≤ C·g(n) by h(n) ≥ 0 yields f(n)h(n) ≤ C·g(n)h(n), so f(n)h(n) = O(g(n)h(n)).

• If f(n)h(n) were O(f(n)), then for large n with f(n)>0 we would have h(n) = O(1). But since h(n) = Theta(g(n)) and g(n) is not O(f(n)), h(n) cannot be bounded by a constant; hence f(n)h(n) is not O(f(n)).

Conclusion: The statement claiming that f(n)h(n) is not O(g(n)h(n)) is false because f(n)h(n) = O(g(n)h(n)). The other statements (f(n) = O(h(n)), f(n) + g(n) = O(h(n)), and f(n)h(n) ≠ O(f(n))) are true under the given hypotheses.