# TADM2E 2.15

From Algorithm Wiki

Revision as of 15:36, 5 November 2016 by Brandon.arnold (Talk | contribs)

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 ac \le bd $ it follows that $ f_1(n) \le {c_3}{g_1(n)}, f_2(n) \le {c_3}{g_2(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)) $