Assume that \(𝑓(𝑛)\) and \(𝑔(𝑛)\) are asymptotically positive. Which of…

Summary: determine which implications are true and give short justifications.

• Statement "f(n)=O(g(n)) and g(n)=O(h(n)) ⇒ f(n)=ω(h(n))": false. Counterexample: take f(n)=n, g(n)=n, h(n)=n. The premises hold but f(n)/h(n)=1, so f(n) is not ω(h(n)). The correct conclusion is f(n)=O(h(n)).

• Statement "f(n)=Ω(g(n)) and g(n)=Ω(h(n)) ⇒ f(n)=O(h(n))": false. From the premises you get f(n)=Ω(h(n)). Example: f(n)=n^2, g(n)=n, h(n)=1 satisfy the premises, but f(n) is not O(h(n)).

• Statement "f(n)=o(g(n)) and g(n)=o(h(n)) ⇒ f(n)=o(h(n))": true. Proof sketch: f(n)/h(n) = (f(n)/g(n))·(g(n)/h(n)), and each factor tends to 0, so the product tends to 0.

• Statement "f(n)=ω(g(n)) and g(n)=ω(h(n)) ⇒ f(n)=Ω(h(n))": true (in fact stronger). Since f(n)/g(n)→∞ and g(n)/h(n)→∞, their product f(n)/h(n)→∞, so f(n)=ω(h(n)), which implies f(n)=Ω(h(n)).

Final verdict: The small-o transitivity statement and the omega-based statement are both true. Therefore both of the statements that assert small-o transitivity and that omega-transitivity implies an Omega relation are correct.