Difference between revisions of "TADM2E 2.13"
From Algorithm Wiki
(We use the additive property, and the definition of Big-O to derive the proof.) |
|||
| Line 1: | Line 1: | ||
| − | + | Choose <math>c_1</math> to satisfy <math>f_1(n) \le {c_1}{g_1(n)}</math> for all <math>n \gt n_{1,0}</math> and <math>c_2</math> to satisfy <math>f_2(n) \le {c_2}{g_2(n)}</math> for all <math>n \gt n_{2,0}</math>. | |
| − | <math>f_1( | ||
| − | <math> | ||
| − | <math> | + | |
| + | Note that <math>c_1</math> and <math>c_2</math> above can be substituted with <math>c_3</math> such that <math>c_3 = max(c_1, c_2)</math> and the conditions still hold. | ||
| + | |||
| + | |||
| + | Since <math>a \le b, c \le d \implies a + b \le c + d</math> it follows that <math>f_1(n) \le {c_3}{g_1(n)}, f_1(n) \le {c_3}{g_1(n)} \implies f_1(n) + f_2(n) \le {c_3}({g_1(n)} + {g_2(n)})</math>. | ||
| + | |||
| + | |||
| + | Therefore <math>f_1(n) + f_2(n) = O(g_1(n) +g_2(n))</math> | ||
Revision as of 20:33, 4 November 2016
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 a + b \le c + d $ 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) + f_2(n) \le {c_3}({g_1(n)} + {g_2(n)}) $.
Therefore $ f_1(n) + f_2(n) = O(g_1(n) +g_2(n)) $
