2
$\begingroup$

let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$

is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?

$\endgroup$

1 Answer 1

3
$\begingroup$

By definition, $f(n) \leq c_1 \cdot g(n)$ and $l(n) \leq c_2 \cdot m(n)$, for some $c_1$ and $n \geq n_0$, and for some $c_2$ and $n \geq n_0'$ respectively. Suppose we set $n_0^* = \max (n_0, n_0')$, then both inequalities are satisfied for $n \geq n_0^*$. Then obviously $f(n) \cdot l(n) \leq c_1 \cdot g(n) \cdot c_2 \cdot m(n)$ for $n \geq n_0^*$. So indeed the claim holds. We can go take one additional step, however. Note that we can replace $c_1 \cdot c_2$ by a new constant, and thus we conclude that $f(n) \cdot l(n) = O(g(n) \cdot m(n))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.