# TADM2E 2.15

Jump to: navigation, search

Choose $c_1$ to satisfy $f_1(n) \le {c_1}{g_1(n)}$ for all $n \gt n_{1,0}$ and $c_2$ to satisfy $f_2(n) \le {c_2}{g_2(n)}$ for all $n \gt n_{2,0}$.

Note that $c_1$ and $c_2$ above can be substituted with $c_3$ such that $c_3 = max(c_1, c_2)$ and the conditions still hold.

Since $a \le b, c \le d \implies ab \le cd$ it follows that $f_1(n) \le {c_3}{g_1(n)}, f_1(n) \le {c_3}{g_1(n)} \implies f_1(n) \times f_2(n) \le {c_3}({g_1(n)} \times {g_2(n)})$.

Therefore $f_1(n) \times f_2(n) = O(g_1(n) \times g_2(n))$