How do you prove that the product of 2 functions is still big O of "h"

Question

This is in my homework and I'm not sure how to do it:

$f \circ g \in O(h^2) \implies f \in O(h) \text{ and } g \in O(h)$.

I get it intuitively but writing it down in proof-form is evading me.

Why is this true, intuitively? – John Douma Jul 26 '17 at 19:24 — John Douma, Jul 26 '17 at 19:24
Hint: try to find counterexamples where $g = h^2/f$. – Robert Israel Jul 26 '17 at 19:34 — Robert Israel, Jul 26 '17 at 19:34

score 0 · Answer 1 · answered Jul 26 '17 at 19:36

0

Can this hold if $f = h^{3/2}$?

answered Jul 26 '17 at 19:36

marty cohen

score 0 · Answer 2 · answered Jul 26 '17 at 19:40

0

Here is a counterexample:

Let $f = log(n)$, $g = n^2, h = n^{3/2}$.

Then $log(n)n^2 = O(n^3)$, but $n^2 \neq O(n^{3/2})$

answered Jul 26 '17 at 19:40

2 Answers2