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))$ ?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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))$.
