Divide and Conquer/Master Theorem - Revision history

Admin: Fix math errors: Big Omega definition missing constant c, set definition using f(n) instead of h(n) and unquantified n_0, non-symmetric notation now in math mode, add missing parentheses around factorial argument, replace \quad with \cdot for multiplication, fix "n >= n0" to proper math mode (via update-page on MediaWiki MCP Server)

2026-06-15T00:16:23Z

Fix math errors: Big Omega definition missing constant c, set definition using f(n) instead of h(n) and unquantified n_0, non-symmetric notation now in math mode, add missing parentheses around factorial argument, replace \quad with \cdot for multiplication, fix "n >= n0" to proper math mode (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 00:16, 15 June 2026
Line 1:		Line 1:


	==Statement of Master Theorem==		==Statement of Master Theorem==

Line 39:		Line 41:
	Big O corresponds roughly to less than or equal to		Big O corresponds roughly to less than or equal to

	Note that this equal sign notation is NOT symmetric - n^3 != O(n^2)		Note that this equal sign notation is NOT symmetric - <math>n^3 \neq O(n^2)</math>

	We can also think about a ''set definition'' - f(n) is in some set of functions that are like g(n)		We can also think about a ''set definition'' - f(n) is in some set of functions that are like g(n)
Line 46:		Line 48:

	<math>		<math>
	\{ h(n) : \exists c > 0, n_0, 0 \leq f(n) \leq c g(n) \}		\{ h(n) : \exists c > 0, n_0 > 0, 0 \leq h(n) \leq c g(n) \}
	</math>		</math>

Line 84:		Line 86:

	<math>		<math>
	\exists c > 0, n_0 > 0 : 0 \leq g(n) \leq f(n)		\exists c > 0, n_0 > 0 : 0 \leq c g(n) \leq f(n)
	</math>		</math>

Line 103:		Line 105:
	</math>		</math>

	for n >~~= n0~~		for <math>n \geq n_0</math>

	==Examples==		==Examples==
Line 222:		Line 224:

	<math>		<math>
	16 \dfrac{n}{4}! \leq c n!		16 \left( \dfrac{n}{4} \right)! \leq c n!
	</math>		</math>

Line 239:		Line 241:

	<math>		<math>
	T(n) = \sqrt{2} \~~quad~~ T \left( \dfrac{n}{2} \right) + \log{n}		T(n) = \sqrt{2} \cdot T \left( \dfrac{n}{2} \right) + \log{n}
	</math>		</math>

Admin: Fix multiple math errors: ε outside log, escaped braces, \exists, log→\log, missing , backward O statement, nonsensical fraction, and typos (via update-page on MediaWiki MCP Server)

2026-06-14T23:20:04Z

Fix multiple math errors: ε outside log, escaped braces, \exists, log→\log, missing </math>, backward O statement, nonsensical fraction, and typos (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:20, 14 June 2026
Line 5:		Line 5:
	'''Case 1: Subproblems Dominate (Leaf-Heavy)'''		'''Case 1: Subproblems Dominate (Leaf-Heavy)'''

	If <math>f(n) = O(n^{ \~~log_{b}{(~~a - \epsilon)} })</math> for some constant <math>\epsilon > 0</math> then <math>T(n) = \Theta( n^{\log_b{a}} )</math>		If <math>f(n) = O( n^{\log_b a - \epsilon} )</math> for some constant <math>\epsilon > 0</math> then <math>T(n) = \Theta( n^{\log_b a} )</math>

	'''Case 2: Split/Recombine ~ Subproblems'''		'''Case 2: Split/Recombine ~ Subproblems'''

	If <math>f(n) = \Theta( n^{\log_b{a}} \log^k~~{(x)}~~ )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log^{k+1} {n} )</math> (note that usually <math>k=0</math>)		If <math>f(n) = \Theta( n^{\log_b a} \log^k n )</math>, then <math>T(n) = \Theta( n^{\log_b a} \log^{k+1} n )</math> (note that usually <math>k=0</math>)

	'''Case 3: Split/Recombine Dominates (Root Heavy)'''		'''Case 3: Split/Recombine Dominates (Root Heavy)'''

	If <math>f(n) = \Omega( n^{\log_b{(a+\epsilon)}} )</math> for some constant <math>\epsilon > 0</math> , and if <math>a f(n/b) \leq cf(n)</math> for some <math>c < 1</math>, then <math>T(n) = \Theta( f(n) )</math>		If <math>f(n) = \Omega( n^{\log_b a + \epsilon} )</math> for some constant <math>\epsilon > 0</math> , and if <math>a f(n/b) \leq cf(n)</math> for some <math>c < 1</math>, then <math>T(n) = \Theta( f(n) )</math>

	==Revisiting Big O, Big Theta, Big Omega==		==Revisiting Big O, Big Theta, Big Omega==
Line 31:		Line 31:
	</math>		</math>

	for all sufficiently large <~~Math~~>n \geq n_0</math>		for all sufficiently large <math>n \geq n_0</math>

	We say that f(n) is ''bounded above'' by g(n).		We say that f(n) is ''bounded above'' by g(n).
Line 46:		Line 46:

	<math>		<math>
	{h(n) : \~~exist~~ c > 0, n_0, 0 \leq f(n) \leq c g(n)}		\{ h(n) : \exists c > 0, n_0, 0 \leq f(n) \leq c g(n) \}
	</math>		</math>

Line 61:		Line 61:
	</math>		</math>

	This means there is a function h(n) in the set O(N2) ~~sucjh~~ that f(n)= n3 + h(n)		This means there is a function h(n) in the set O(n^2) such that f(n) = n^3 + h(n)

	they represent SOME func in that set		they represent SOME func in that set
Line 71:		Line 71:
	</math>		</math>

	is a true statement, but the reverse is not ~~ture~~.		is a true statement, but the reverse is not true.

	This means, for any f(n) in O(n), there exists some function g(n) in O(n^2) such that if you add n^2 to the function f(n), you get g(n).		This means, for any f(n) in O(n), there exists some function g(n) in O(n^2) such that if you add n^2 to the function f(n), you get g(n).
Line 94:		Line 94:

	<math>		<math>
	f(n) = \Theta( g(n) ) = \Omega( g(n) ) \~~bigcap~~ O(g(n))		f(n) = \Theta( g(n) ) = \Omega( g(n) ) \cap O(g(n))
	</math>		</math>

Line 118:		Line 118:

	<math>		<math>
	\log_{b}{a} = log_{2}{2} = 1		\log_{b}{a} = \log_{2}{2} = 1
	</math>		</math>

Line 128:		Line 128:

	<math>		<math>
	f(n) = \Theta( n^c \log^{k}{n} )		f(n) = \Theta( n^c \log^{k} n )
	</math>		</math>

Line 144:		Line 144:

	<math>		<math>
	T(n) = 2 T(\frac{n}{2}) + \frac{n}{log n}		T(n) = 2 T(\frac{n}{2}) + \frac{n}{\log n}
	</math>		</math>

Line 158:		Line 158:

	<math>		<math>
	c = \log_b{a} = log_{4}{2} = \frac{1}{2}		c = \log_b{a} = \log_{4}{2} = \frac{1}{2}
	</math>		</math>

Line 171:		Line 171:
	so we have Case 3		so we have Case 3

	WE need to check the regularity condition:		We need to check the regularity condition:

	<math>		<math>
Line 178:		Line 178:

	<math>		<math>
	\~~dfrac~~{2}{~~2 + \dots~~} n^{0.51} < c n^{0.51}		\frac{2}{4^{0.51}} n^{0.51} < c n^{0.51}
	</math>		</math>

Line 206:		Line 206:

	<math>		<math>
	a = 16, b = 4, c = log_{b}{a} = 2		a = 16, b = 4, c = \log_{b}{a} = 2
	</math>		</math>

Line 219:		Line 219:
	<math>		<math>
	16 f(\frac{n}{4}) \leq c f(n)		16 f(\frac{n}{4}) \leq c f(n)
	<math>		</math>

	<math>		<math>
Line 243:		Line 243:

	<math>		<math>
	a = \sqrt{2} = 2^{\frac{1}{2}}, b = 2, \log_{2}{(2^{\frac{1}{2}}} = \frac{1}{2}		a = \sqrt{2} = 2^{\frac{1}{2}}, b = 2, \log_{2}{2^{\frac{1}{2}}} = \frac{1}{2}
	</math>		</math>

	Now we compare <math>f(n) = \log{n}</math> with <math>n^c = n^{\frac{1}{2}}</math>		Now we compare <math>f(n) = \log{n}</math> with <math>n^c = n^{\frac{1}{2}}</math>

	If we compare the graphs of these two functions, the square root grows slightly faster: <math>\~~sqrt~~{n} = O(\~~log~~{n})</math>		If we compare the graphs of these two functions, the square root grows slightly faster: <math>\log{n} = O(\sqrt{n})</math>

	That means <math>n^c</math> provides an upper bound, and <math>f(n) = O(n^c) = O(\sqrt{n})</math>		That means <math>n^c</math> provides an upper bound, and <math>f(n) = O(n^c) = O(\sqrt{n})</math>
Line 266:		Line 266:
	</math>		</math>

	Using values of a and b, <math>\log_{b}{a} = \~~log~~{3} \approx 1.5</math>		Using values of a and b, <math>\log_{b}{a} = \log_2{3} \approx 1.5</math>

	Now we compare <math>f(n) = n</math> with <math>n^{\~~log~~{3}}</math>		Now we compare <math>f(n) = n</math> with <math>n^{\log_2{3}}</math>

	<math>		<math>
Line 276:		Line 276:
	Therefore we have Case 1:		Therefore we have Case 1:

	<~~Math~~>		<math>
	T(n) = \Theta(n^{\~~log~~{3}})		T(n) = \Theta(n^{\log_2{3}})
	</math>		</math>

Admin: /* Flags */

2017-07-16T09:07:06Z

Flags

← Older revision		Revision as of 09:07, 16 July 2017
Line 283:		Line 283:

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

			[[Category:Divide and Conquer]]
			[[Category:Master Theorem]]

Admin: /* Example 6 */

2017-07-16T09:06:31Z

Example 6

@@ Line 239: / Line 239: @@
 <math>
-T(n) = \sqrt{2} T \left( \dfrac{n}{2} \right) + \log{n}
+T(n) = \sqrt{2} \quad T \left( \dfrac{n}{2} \right) + \log{n}
 </math>
@@ Line 258: / Line 258: @@
 <math>
 T(n) = \Theta(\sqrt{n})
 </math>

Admin: /* Example 6 */

2017-07-16T09:03:31Z

Example 6

← Older revision		Revision as of 09:03, 16 July 2017
Line 239:		Line 239:

	<math>		<math>
	T(n) = \sqrt{2} + \left( \dfrac{n}{2} \right) + \log{n}		T(n) = \sqrt{2} T \left( \dfrac{n}{2} \right) + \log{n}
	</math>		</math>

Admin: /* Example 5 */

2017-07-16T09:03:08Z

Example 5

@@ Line 233: / Line 233: @@
 <math>
 T(n) = \Theta(n!)
 </math>

Admin: /* Example 4 */

2017-07-16T09:00:06Z

Example 4

@@ Line 196: / Line 196: @@
 Careful - this case does not apply! <math>a < 1</math> violates one of the assumptions of the theorem.
 =Flags=
 {{AlgorithmsFlag}}

Admin: /* Example 4 */

2017-07-16T08:57:21Z

Example 4

← Older revision		Revision as of 08:57, 16 July 2017
Line 190:		Line 190:

	===Example 4===		===Example 4===

			<math>
			T(n) = 0.5 T(\frac{n}{2}) + \frac{1}{n}
			</math>

			Careful - this case does not apply! <math>a < 1</math> violates one of the assumptions of the theorem.

	=Flags=		=Flags=

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin: /* Example 3 */

2017-07-16T08:55:42Z

Example 3

← Older revision		Revision as of 08:55, 16 July 2017
Line 174:		Line 174:

	<math>		<math>
	~~\begin{array}~~		2 f( \frac{n}{4} ) \leq c f(n)
	2 f( \frac{n}{4} ) & \leq & c f(n) \\		</math>
	\dfrac{2}{2 + \dots} n^{0.51} & < & c n^{0.51}
			<math>
			\dfrac{2}{2 + \dots} n^{0.51} < c n^{0.51}
	</math>		</math>

Admin: /* Example 1 */

2017-07-16T08:55:13Z

Example 1

← Older revision		Revision as of 08:55, 16 July 2017
Line 118:		Line 118:

	<math>		<math>
	~~\begin{array}~~		\log_{b}{a} = log_{2}{2} = 1
	\log_{b}{a} &=& log_{2}{2} = 1 \\		</math>
	n^c &=& n
	~~\end{array}~~		<math>
			n^c = n
	</math>		</math>

Line 140:		Line 141:
	This corresponds to the case where the function <math>n^c</math>, which represents the computational cost of solving the subproblems, grows at the same rate as the merge step, f(n), which in this case was 10n.		This corresponds to the case where the function <math>n^c</math>, which represents the computational cost of solving the subproblems, grows at the same rate as the merge step, f(n), which in this case was 10n.

	===Example 2===		===Example 2===

	<math>		<math>