Divide and Conquer - Revision history

Admin: Fix Master Theorem math: ε moved outside log (Cases 1 & 3), x→n (Case 2), remove bad spacing in \log^{k+1} {n} (via update-page on MediaWiki MCP Server)

2026-06-14T23:19:44Z

Fix Master Theorem math: ε moved outside log (Cases 1 & 3), x→n (Case 2), remove bad spacing in \log^{k+1} {n} (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:19, 14 June 2026
Line 46:		Line 46:

	Here, the sub-problems are broken down into smaller number <math>a</math> of pieces of size <math>\frac{n}{b}</math>.		Here, the sub-problems are broken down into smaller number <math>a</math> of pieces of size <math>\frac{n}{b}</math>.

	~~===The Master Theorem===~~

	~~{{Main\|Divide and Conquer/Master Theorem}}~~

	~~The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:~~

	'''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>

	See [[Divide and Conquer/Master Theorem]] for examples.		See [[Divide and Conquer/Master Theorem]] for examples.

Admin: /* The Master Theorem */

2017-08-09T21:22:51Z

The Master Theorem

← Older revision		Revision as of 21:22, 9 August 2017
Line 49:		Line 49:
	===The Master Theorem===		===The Master Theorem===

	{{Main\|Master Theorem}}		{{Main\|Divide and Conquer/Master Theorem}}

	The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:		The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

Admin: /* The Master Theorem */

2017-08-09T21:22:37Z

The Master Theorem

← Older revision		Revision as of 21:22, 9 August 2017
Line 48:		Line 48:

	===The Master Theorem===		===The Master Theorem===

			{{Main\|Master Theorem}}

	The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:		The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

Admin: /* The Master Theorem */

2017-07-16T08:16:52Z

The Master Theorem

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

	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>

			See [[Divide and Conquer/Master Theorem]] for examples.

	=Resources=		=Resources=

Admin: /* The Master Theorem */

2017-07-16T08:16:28Z

The Master Theorem

← Older revision		Revision as of 08:16, 16 July 2017
Line 57:		Line 57:
	'''Case 2: Split/Recombine ~ Subproblems'''		'''Case 2: Split/Recombine ~ Subproblems'''

	If <math>f(n) = \Theta( n^{\log_b{a}} )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log{n} )</math>		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>)

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

Admin: /* The Master Theorem */

2017-07-16T06:59:51Z

The Master Theorem

← Older revision		Revision as of 06:59, 16 July 2017
Line 51:		Line 51:
	The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:		The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

	'''Case 1:'''		'''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:'''		'''Case 2: Split/Recombine ~ Subproblems'''

	If <math>f(n) = \Theta( n^{\log_b{a}} )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log{n} )</math>		If <math>f(n) = \Theta( n^{\log_b{a}} )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log{n} )</math>

	'''Case 3:'''		'''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>

Admin: /* The Master Theorem */

2017-07-16T06:57:29Z

The Master Theorem

← Older revision		Revision as of 06:57, 16 July 2017
Line 51:		Line 51:
	The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:		The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

	1. 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-\epsilon)}} )</math>		'''Case 1:'''

			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:'''

			If <math>f(n) = \Theta( n^{\log_b{a}} )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log{n} )</math>

			'''Case 3:'''

			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>

	=Resources=		=Resources=

Admin: /* Recurrence Relations */

2017-07-16T06:54:55Z

Recurrence Relations

@@ Line 32: / Line 32: @@
 a_{n} = n a_{n-1}, a_1 = 1 \rightarrow a_n = n!
 </math>
 =Resources=

Admin: /* Resources */

2017-07-16T06:33:57Z

Resources

← Older revision		Revision as of 06:33, 16 July 2017
Line 44:		Line 44:

	Advanced dynamic programming and divide-and-conquer: https://www.youtube.com/watch?v=Tw1k46ywN6E		Advanced dynamic programming and divide-and-conquer: https://www.youtube.com/watch?v=Tw1k46ywN6E



	=Flags=		=Flags=

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin: /* Skiena Chapter 4 */

2017-07-16T06:33:41Z

Skiena Chapter 4

← Older revision		Revision as of 06:33, 16 July 2017
Line 4:		Line 4:

	Powerful technique for solving problems - break problems down into smaller problems.		Powerful technique for solving problems - break problems down into smaller problems.

			The basic idea behind divide and conquer is, you are looking for a problem where it is faster to solve the problem in pieces AND TO MERGE THE PIECES than it is to solve the overall problem.

			Merge sort is a good example of divide and conquer: merge must take less time than solving the two subproblems, which will make the algorithm efficient overall. Merge sort is just merging two lists, which is O(n), and getting each of the lists costs O(n log n).

			Analyzing divide-and conquer algorithms depends on solving the asymptotic behavior of the divide-and-conquer algorithm's recurrence relations.

			===Recurrence Relations===

			A recurrence relation is an alternative representation for functions. (Somewhat related is Stephen Wolfram's idea that the universe is fundamentally digital, and that we need cellular autonoma and self-replicating patterns, to effectively understand and describe the world.)

			We can represent a polynomial using a recurrence. Multiplication is achieved by having a recurrence relation in which things are added together:

			<math>
			a_n = a_{n-1} + 1, a_1 = 1 \rightarrow a_n = n
			</math>

			We can also represent exponential functions by multiplying successive terms together:

			<math>
			a_n = 2 a_{n-1}, a_1 = 1 \rightarrow a_n = 2^{n-1}
			</math>

			We can also describe more unusual, or harder-to-describe, functions, like the factorial function, with very succinct notation:

			<math>
			a_{n} = n a_{n-1}, a_1 = 1 \rightarrow a_n = n!
			</math>

	=Resources=		=Resources=