TADM2E 2.13 - Revision history

Brandon.arnold at 15:35, 5 November 2016

2016-11-05T15:35:10Z

Brandon.arnold at 20:36, 4 November 2016

2016-11-04T20:36:18Z

Brandon.arnold at 20:33, 4 November 2016

2016-11-04T20:33:03Z

Kmckernan: We use the additive property, and the definition of Big-O to derive the proof.

2016-09-21T01:59:53Z

We use the additive property, and the definition of Big-O to derive the proof.

New page

By Definition of Big-O we note that
<math>f_1(x) + f_2(x) = O(g_1(x)) + O(g_2(x))</math> and that this is equivalent to,
<math>f_1(x) + f_2(x) = O(max(g_1(x)) + O(g_2(x)))</math> which is equivalent to,

<math>O(max(g_1(x)) + O(g_2(x))) = O(g_1(x)+g_2(x))</math> QED.

← Older revision		Revision as of 15:35, 5 November 2016
Line 5:		Line 5:


−	Since <math>a \le b, c \le d \implies a + c \le b + 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>.	+	Since <math>a \le b, c \le d \implies a + c \le b + d</math> it follows that <math>f_1(n) \le {c_3}{g_1(n)}, f_2(n) \le {c_3}{g_2(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>		Therefore <math>f_1(n) + f_2(n) = O(g_1(n) +g_2(n))</math>

← Older revision		Revision as of 20:36, 4 November 2016
Line 5:		Line 5:


−	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>.	+	Since <math>a \le b, c \le d \implies a + c \le b + 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>		Therefore <math>f_1(n) + f_2(n) = O(g_1(n) +g_2(n))</math>

← Older revision		Revision as of 20:33, 4 November 2016
Line 1:		Line 1:
−	~~By Definition of Big-O we note that~~	+	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(~~x) + f_2(x~~) ~~= O(~~g_1(~~x)) + O(g_2(x)~~)</math> and ~~that this is equivalent~~ to,
−	<math>~~f_1(x) +~~ f_2(x) ~~= O(max(g_1(x)) + O(~~g_2(~~x))~~)</math> ~~which is equivalent to~~,

−	<math>O(~~max~~(g_1(x)) + O(g_2(x))) = O(g_1(x)+g_2(x))</math> ~~QED.~~	+
		+	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>