Master theorem (analysis of algorithms) - Revision history

Zhermes: /* Introduction */ clarify what variable 'b' is

2025-02-27T18:28:05Z

Introduction: clarify what variable 'b' is

← Previous revision		Revision as of 18:28, 27 February 2025
Line 16:		Line 16:

	[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]		[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]
	The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.		The above algorithm divides the problem into a number ({{math\|''a''}}) of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. The factor by which the size of subproblems is reduced ({{math\|''b''}}) need not, in general, be the same as the number of subproblems ({{math\|''a''}}). Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

	The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]		The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]

Stickymatch: Reverting edit(s) by 129.22.1.25 (talk) to rev. 1275810350 by Kavigupta: Vandalism (UV 0.1.6)

2025-02-21T03:16:51Z

Reverting edit(s) by 129.22.1.25 (talk) to rev. 1275810350 by Kavigupta: Vandalism (UV 0.1.6)

← Previous revision		Revision as of 03:16, 21 February 2025
Line 45:		Line 45:
	\|-		\|-

			! 1
	! 1 (Christmas tree)
	\| Work to split/recombine a problem is dominated by subproblems.		\| Work to split/recombine a problem is dominated by subproblems.

Line 61:		Line 61:
	\|-		\|-

			! 2
	! 2 (Rectangle)
	\| Work to split/recombine a problem is comparable to subproblems.		\| Work to split/recombine a problem is comparable to subproblems.
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for a <math>k \ge 0</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for a <math>k \ge 0</math>
Line 77:		Line 77:
	\|-		\|-

	! 3 ~~(Chad)~~		! 3
	\| Work to split/recombine a problem dominates subproblems.		\| Work to split/recombine a problem dominates subproblems.

129.22.1.25: /* Generic form */

2025-02-21T03:16:22Z

Generic form

← Previous revision		Revision as of 03:16, 21 February 2025
Line 45:		Line 45:
	\|-		\|-

			! 1 (Christmas tree)
	! 1
	\| Work to split/recombine a problem is dominated by subproblems.		\| Work to split/recombine a problem is dominated by subproblems.

Line 61:		Line 61:
	\|-		\|-

			! 2 (Rectangle)
	! 2
	\| Work to split/recombine a problem is comparable to subproblems.		\| Work to split/recombine a problem is comparable to subproblems.
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for a <math>k \ge 0</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for a <math>k \ge 0</math>
Line 77:		Line 77:
	\|-		\|-

	! 3		! 3 (Chad)
	\| Work to split/recombine a problem dominates subproblems.		\| Work to split/recombine a problem dominates subproblems.

Kavigupta: /* Generic form */ Clarified notation. While log^k n is standard notation, it is potentially confusing to newcomers who expect the exponent to be applied to the operator and not the output of the expression.

2025-02-15T05:41:15Z

Generic form: Clarified notation. While log^k n is standard notation, it is potentially confusing to newcomers who expect the exponent to be applied to the operator and not the output of the expression.

Dewritech: clean up, typo(s) fixed: widely- → widely

2024-12-07T21:15:40Z

clean up, typo(s) fixed: widely- → widely

DataSculptor: /* Generic form */ Clearer wording

2024-12-02T08:40:28Z

Generic form: Clearer wording

← Previous revision		Revision as of 08:40, 2 December 2024
Line 47:		Line 47:

	! 1		! 1
	\| Work to split/recombine a problem is ~~dwarfed~~ by subproblems.		\| Work to split/recombine a problem is dominated by subproblems.

	i.e. the recursion tree is leaf-heavy		i.e. the recursion tree is leaf-heavy.
	\| When <math>f(n) = O(n^{c})</math> where <math>c<c_{\operatorname{crit}}</math>		\| When <math>f(n) = O(n^{c})</math> where <math>c<c_{\operatorname{crit}}</math>

Helpful Raccoon: link to "tree" instead of "solution tree"

2024-10-03T21:07:29Z

link to "tree" instead of "solution tree"

← Previous revision		Revision as of 21:07, 3 October 2024
Line 16:		Line 16:

	[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]		[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]
	The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its [[~~solution~~ tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.		The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

	The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]		The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]

Polycrove: updated parenthetical to latex

2024-08-31T23:55:30Z

updated parenthetical to latex

← Previous revision		Revision as of 23:55, 31 August 2024
Line 30:		Line 30:
	The master theorem always yields [[asymptotically tight bound]]s to recurrences from [[divide and conquer algorithm]]s that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If <math>T(n)</math> denotes the total time for the algorithm on an input of size <math>n</math>, and <math>f(n)</math> denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a [[recurrence relation]] that takes the form:		The master theorem always yields [[asymptotically tight bound]]s to recurrences from [[divide and conquer algorithm]]s that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If <math>T(n)</math> denotes the total time for the algorithm on an input of size <math>n</math>, and <math>f(n)</math> denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a [[recurrence relation]] that takes the form:
	:<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math>		:<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math>
	Here <math>n</math> is the size of an input problem, <math>a</math> is the number of subproblems in the recursion, and <math>b</math> is the factor by which the subproblem size is reduced in each recursive call (b>1). Crucially, <math>a</math> and <math>b</math> must not depend on <math>n</math>. The theorem below also assumes that, as a base case for the recurrence, <math>T(n)=\Theta(1)</math> when <math>n</math> is less than some bound <math>\kappa > 0</math>, the smallest input size that will lead to a recursive call.		Here <math>n</math> is the size of an input problem, <math>a</math> is the number of subproblems in the recursion, and <math>b</math> is the factor by which the subproblem size is reduced in each recursive call (<math>b > 1</math>). Crucially, <math>a</math> and <math>b</math> must not depend on <math>n</math>. The theorem below also assumes that, as a base case for the recurrence, <math>T(n)=\Theta(1)</math> when <math>n</math> is less than some bound <math>\kappa > 0</math>, the smallest input size that will lead to a recursive call.

	Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem <math>f(n)</math> relates to the ''critical exponent'' <math>c_{\operatorname{crit}}=\log_b a</math>. (The table below uses standard [[big O notation]]).		Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem <math>f(n)</math> relates to the ''critical exponent'' <math>c_{\operatorname{crit}}=\log_b a</math>. (The table below uses standard [[big O notation]]).

LucasBrown: Changing short description from "Analysis of divide and conquer algorithms" to "Tool for analyzing divide-and-conquer algorithms"

2024-07-28T01:38:58Z

Changing short description from "Analysis of divide and conquer algorithms" to "Tool for analyzing divide-and-conquer algorithms"

← Previous revision		Revision as of 01:38, 28 July 2024
Line 1:		Line 1:
	{{Short description\|~~Analysis~~ of divide and conquer algorithms}}		{{Short description\|Tool for analyzing divide-and-conquer algorithms}}
	In the [[analysis of algorithms]], the '''master theorem for divide-and-conquer recurrences''' provides an [[asymptotic analysis]] for many [[recurrence relation]]s that occur in the [[Analysis of algorithms\|analysis]] of [[divide and conquer algorithm\|divide-and-conquer algorithm]]s. The approach was first presented by [[Jon Bentley (computer scientist)\|Jon Bentley]], [[Dorothea Blostein]] (née Haken), and [[James B. Saxe]] in 1980, where it was described as a "unifying method" for solving such recurrences.<ref>{{citation \| last1 = Bentley \| first1 = Jon Louis \| author1-link = Jon Bentley (computer scientist) \| last2 = Haken \| first2 = Dorothea \| author2-link = Dorothea Blostein \| last3 = Saxe \| first3 = James B. \| author3-link = James B. Saxe \| date = September 1980 \| doi = 10.1145/1008861.1008865 \| issue = 3 \| journal = [[ACM SIGACT News]] \| pages = 36–44 \| title = A general method for solving divide-and-conquer recurrences \| volume = 12\| s2cid = 40642274 \| url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| archive-url = https://web.archive.org/web/20170922231154/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| url-status = dead \| archive-date = September 22, 2017 }}</ref> The name "master theorem" was popularized by the widely-used algorithms textbook ''[[Introduction to Algorithms]]'' by [[Thomas H. Cormen\|Cormen]], [[Charles E. Leiserson\|Leiserson]], [[Ron Rivest\|Rivest]], and [[Clifford Stein\|Stein]].		In the [[analysis of algorithms]], the '''master theorem for divide-and-conquer recurrences''' provides an [[asymptotic analysis]] for many [[recurrence relation]]s that occur in the [[Analysis of algorithms\|analysis]] of [[divide and conquer algorithm\|divide-and-conquer algorithm]]s. The approach was first presented by [[Jon Bentley (computer scientist)\|Jon Bentley]], [[Dorothea Blostein]] (née Haken), and [[James B. Saxe]] in 1980, where it was described as a "unifying method" for solving such recurrences.<ref>{{citation \| last1 = Bentley \| first1 = Jon Louis \| author1-link = Jon Bentley (computer scientist) \| last2 = Haken \| first2 = Dorothea \| author2-link = Dorothea Blostein \| last3 = Saxe \| first3 = James B. \| author3-link = James B. Saxe \| date = September 1980 \| doi = 10.1145/1008861.1008865 \| issue = 3 \| journal = [[ACM SIGACT News]] \| pages = 36–44 \| title = A general method for solving divide-and-conquer recurrences \| volume = 12\| s2cid = 40642274 \| url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| archive-url = https://web.archive.org/web/20170922231154/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| url-status = dead \| archive-date = September 22, 2017 }}</ref> The name "master theorem" was popularized by the widely-used algorithms textbook ''[[Introduction to Algorithms]]'' by [[Thomas H. Cormen\|Cormen]], [[Charles E. Leiserson\|Leiserson]], [[Ron Rivest\|Rivest]], and [[Clifford Stein\|Stein]].

Bosshafter Boss: /* Inadmissible equations / Removed incorrect example with reasoning mentioned nowhere else in the article. (T(n) is asymptomatically 4/3n as one would expect from applying case 3)

2024-06-26T05:08:38Z

Inadmissible equations: Removed incorrect example with reasoning mentioned nowhere else in the article. (T(n) is asymptomatically 4/3*n as one would expect from applying case 3)

← Previous revision		Revision as of 05:08, 26 June 2024
Line 217:		Line 217:
	*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>		*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>
	*:non-polynomial difference between <math>f(n)</math> and <math>n^{\log_b a}</math> (see below; extended version applies)		*:non-polynomial difference between <math>f(n)</math> and <math>n^{\log_b a}</math> (see below; extended version applies)
	*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
	*:<math> a<1 </math> cannot have less than one sub problem
	*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>		*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
	*:<math>f(n)</math>, which is the combination time, is not positive		*:<math>f(n)</math>, which is the combination time, is not positive

← Previous revision		Revision as of 18:28, 27 February 2025
Line 16:		Line 16:

	[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]		[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]
	The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.		The above algorithm divides the problem into a number ({{math\|''a''}}) of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. The factor by which the size of subproblems is reduced ({{math\|''b''}}) need not, in general, be the same as the number of subproblems ({{math\|''a''}}). Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

	The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]		The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]

← Previous revision		Revision as of 21:07, 3 October 2024
Line 16:		Line 16:

	[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]		[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]
	The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its [[~~solution~~ tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.		The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

	The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]		The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]

← Previous revision		Revision as of 05:41, 15 February 2025
Line 32:		Line 32:
	Here <math>n</math> is the size of an input problem, <math>a</math> is the number of subproblems in the recursion, and <math>b</math> is the factor by which the subproblem size is reduced in each recursive call (<math>b > 1</math>). Crucially, <math>a</math> and <math>b</math> must not depend on <math>n</math>. The theorem below also assumes that, as a base case for the recurrence, <math>T(n)=\Theta(1)</math> when <math>n</math> is less than some bound <math>\kappa > 0</math>, the smallest input size that will lead to a recursive call.		Here <math>n</math> is the size of an input problem, <math>a</math> is the number of subproblems in the recursion, and <math>b</math> is the factor by which the subproblem size is reduced in each recursive call (<math>b > 1</math>). Crucially, <math>a</math> and <math>b</math> must not depend on <math>n</math>. The theorem below also assumes that, as a base case for the recurrence, <math>T(n)=\Theta(1)</math> when <math>n</math> is less than some bound <math>\kappa > 0</math>, the smallest input size that will lead to a recursive call.

	Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem <math>f(n)</math> relates to the ''critical exponent'' <math>c_{\operatorname{crit}}=\log_b a</math>. (The table below uses standard [[big O notation]]).		Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem <math>f(n)</math> relates to the ''critical exponent'' <math>c_{\operatorname{crit}}=\log_b a</math>. (The table below uses standard [[big O notation]]). Throughout, <math>(\log n)^k</math> is used for clarity, though in textbooks this is usually rendered <math>\log^k n</math>.

	:<math>c_{\operatorname{crit}} = \log_b a = \log(\#\text{subproblems})/\log(\text{relative subproblem size})</math>		:<math>c_{\operatorname{crit}} = \log_b a = \log(\#\text{subproblems})/\log(\text{relative subproblem size})</math>
Line 63:		Line 63:
	! 2		! 2
	\| Work to split/recombine a problem is comparable to subproblems.		\| Work to split/recombine a problem is comparable to subproblems.
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> for a <math>k \ge 0</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for a <math>k \ge 0</math>

	(rangebound by the critical-exponent polynomial, times zero or more optional <math>\log</math>s)		(rangebound by the critical-exponent polynomial, times zero or more optional <math>\log</math>s)

	\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>		\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} (\log n)^{k+1} \right)</math>

	(The bound is the splitting term, where the log is augmented by a single power.)		(The bound is the splitting term, where the log is augmented by a single power.)
Line 73:		Line 73:
	\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2})</math>, then <math>T(n) = \Theta(n^{1/2} \log n)</math>.		\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2})</math>, then <math>T(n) = \Theta(n^{1/2} \log n)</math>.

	If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2} \log n)</math>, then <math>T(n) = \Theta(n^{1/2} \log~~^{2}~~ n)</math>.		If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2} \log n)</math>, then <math>T(n) = \Theta(n^{1/2} (\log n)^2)</math>.

	\|-		\|-
Line 111:		Line 111:

	! 2a		! 2a
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> for any <math>k > -1</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for any <math>k > -1</math>

	\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>		\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} (\log n)^{k+1} \right)</math>

	(The bound is the splitting term, where the log is augmented by a single power.)		(The bound is the splitting term, where the log is augmented by a single power.)

	\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2}/\log^{1/2} n)</math>, then <math>T(n) = \Theta(n^{1/2} \log^{1/2} n)</math>.		\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2}/(\log n)^{1/2})</math>, then <math>T(n) = \Theta(n^{1/2} (\log n)^{1/2})</math>.

	\|-		\|-

	! 2b		! 2b
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> for <math>k = -1</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for <math>k = -1</math>

	\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log \log n \right)</math>		\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log \log n \right)</math>
Line 133:		Line 133:

	! 2c		! 2c
	\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> for any <math>k < -1</math>		\| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}(\log n)^{k})</math> for any <math>k < -1</math>

	\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>		\| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>
Line 139:		Line 139:
	(The bound is the splitting term, where the log disappears.)		(The bound is the splitting term, where the log disappears.)

	\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2}/\log^2 n)</math>, then <math>T(n) = \Theta(n^{1/2})</math>.		\| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2}/(\log n)^2)</math>, then <math>T(n) = \Theta(n^{1/2})</math>.

	\|}		\|}
Line 168:		Line 168:

	:<math>a = 2, \, b = 2, \, c = 1, \, f(n) = 10n</math>		:<math>a = 2, \, b = 2, \, c = 1, \, f(n) = 10n</math>
	:<math>f(n) = \Theta\left(n^{c} \log^{k} n\right)</math> where <math>c = 1, k = 0</math>		:<math>f(n) = \Theta\left(n^{c} (\log n)^{k}\right)</math> where <math>c = 1, k = 0</math>
	Next, we see if we satisfy the case 2 condition:		Next, we see if we satisfy the case 2 condition:
	:<math>\log_b a = \log_2 2 = 1</math>, and therefore, c and <math>\log_b a</math> are equal		:<math>\log_b a = \log_2 2 = 1</math>, and therefore, c and <math>\log_b a</math> are equal
Line 174:		Line 174:
	So it follows from the second case of the master theorem:		So it follows from the second case of the master theorem:

	:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math>		:<math>T(n) = \Theta\left( n^{\log_b a} (\log n)^{k+1}\right) = \Theta\left( n^{1} (\log n)^{1}\right) = \Theta\left(n \log n\right)</math>

	Thus the given recurrence relation <math>T(n)</math> was in <math>\Theta(n \log n)</math>.		Thus the given recurrence relation <math>T(n)</math> was in <math>\Theta(n \log n)</math>.

← Previous revision		Revision as of 21:15, 7 December 2024
Line 1:		Line 1:
	{{Short description\|Tool for analyzing divide-and-conquer algorithms}}		{{Short description\|Tool for analyzing divide-and-conquer algorithms}}
	In the [[analysis of algorithms]], the '''master theorem for divide-and-conquer recurrences''' provides an [[asymptotic analysis]] for many [[recurrence relation]]s that occur in the [[Analysis of algorithms\|analysis]] of [[divide and conquer algorithm\|divide-and-conquer algorithm]]s. The approach was first presented by [[Jon Bentley (computer scientist)\|Jon Bentley]], [[Dorothea Blostein]] (née Haken), and [[James B. Saxe]] in 1980, where it was described as a "unifying method" for solving such recurrences.<ref>{{citation \| last1 = Bentley \| first1 = Jon Louis \| author1-link = Jon Bentley (computer scientist) \| last2 = Haken \| first2 = Dorothea \| author2-link = Dorothea Blostein \| last3 = Saxe \| first3 = James B. \| author3-link = James B. Saxe \| date = September 1980 \| doi = 10.1145/1008861.1008865 \| issue = 3 \| journal = [[ACM SIGACT News]] \| pages = 36–44 \| title = A general method for solving divide-and-conquer recurrences \| volume = 12\| s2cid = 40642274 \| url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| archive-url = https://web.archive.org/web/20170922231154/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| url-status = dead \| archive-date = September 22, 2017 }}</ref> The name "master theorem" was popularized by the widely-used algorithms textbook ''[[Introduction to Algorithms]]'' by [[Thomas H. Cormen\|Cormen]], [[Charles E. Leiserson\|Leiserson]], [[Ron Rivest\|Rivest]], and [[Clifford Stein\|Stein]].		In the [[analysis of algorithms]], the '''master theorem for divide-and-conquer recurrences''' provides an [[asymptotic analysis]] for many [[recurrence relation]]s that occur in the [[Analysis of algorithms\|analysis]] of [[divide and conquer algorithm\|divide-and-conquer algorithm]]s. The approach was first presented by [[Jon Bentley (computer scientist)\|Jon Bentley]], [[Dorothea Blostein]] (née Haken), and [[James B. Saxe]] in 1980, where it was described as a "unifying method" for solving such recurrences.<ref>{{citation \| last1 = Bentley \| first1 = Jon Louis \| author1-link = Jon Bentley (computer scientist) \| last2 = Haken \| first2 = Dorothea \| author2-link = Dorothea Blostein \| last3 = Saxe \| first3 = James B. \| author3-link = James B. Saxe \| date = September 1980 \| doi = 10.1145/1008861.1008865 \| issue = 3 \| journal = [[ACM SIGACT News]] \| pages = 36–44 \| title = A general method for solving divide-and-conquer recurrences \| volume = 12\| s2cid = 40642274 \| url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| archive-url = https://web.archive.org/web/20170922231154/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 \| url-status = dead \| archive-date = September 22, 2017 }}</ref> The name "master theorem" was popularized by the widely used algorithms textbook ''[[Introduction to Algorithms]]'' by [[Thomas H. Cormen\|Cormen]], [[Charles E. Leiserson\|Leiserson]], [[Ron Rivest\|Rivest]], and [[Clifford Stein\|Stein]].

	Not all recurrence relations can be solved by this theorem; its generalizations include the [[Akra–Bazzi method]].		Not all recurrence relations can be solved by this theorem; its generalizations include the [[Akra–Bazzi method]].
Line 16:		Line 16:

	[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]		[[File:Recursive_problem_solving.svg\|thumb\|right\|359x359px\|Solution tree.]]
	The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.		The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size {{math\|''n''/''b''}}. Its solution [[Tree (abstract data type)\|tree]] has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than ''k'') that do not recurse. The above example would have {{mvar\|a}} child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem {{mvar\|n}} passed to that instance of the recursive call and given by <math>f(n)</math>. The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

	The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]		The runtime of an algorithm such as the {{mvar\|p}} above on an input of size {{mvar\|n}}, usually denoted <math>T(n)</math>, can be expressed by the [[recurrence relation]]
Line 44:		Line 44:
	! width=400\|Notational examples		! width=400\|Notational examples
	\|-		\|-


	! 1		! 1
	\| Work to split/recombine a problem is dominated by subproblems.		\| Work to split/recombine a problem is dominated by subproblems.

	i.e. the recursion tree is leaf-heavy.		i.e. the recursion tree is leaf-heavy.
	\| When <math>f(n) = O(n^{c})</math> where <math>c<c_{\operatorname{crit}}</math>		\| When <math>f(n) = O(n^{c})</math> where <math>c<c_{\operatorname{crit}}</math>

	(upper-bounded by a lesser exponent polynomial)		(upper-bounded by a lesser exponent polynomial)
Line 61:		Line 60:

	\|-		\|-


	! 2		! 2
Line 78:		Line 76:

	\|-		\|-


	! 3		! 3
	\| Work to split/recombine a problem dominates subproblems.		\| Work to split/recombine a problem dominates subproblems.

	i.e. the recursion tree is root-heavy.		i.e. the recursion tree is root-heavy.
	\| When <math>f(n) = \Omega(n^{c})</math> where <math>c>c_{\operatorname{crit}}</math>		\| When <math>f(n) = \Omega(n^{c})</math> where <math>c>c_{\operatorname{crit}}</math>

	(lower-bounded by a greater-exponent polynomial)		(lower-bounded by a greater-exponent polynomial)

	\| ... this doesn't necessarily yield anything. Furthermore, if		\| ... this doesn't necessarily yield anything. Furthermore, if

	:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for some constant <math>k < 1</math> and all sufficiently large <math>n</math> (often called the ''regularity condition'')		:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for some constant <math>k < 1</math> and all sufficiently large <math>n</math> (often called the ''regularity condition'')
Line 177:		Line 174:
	So it follows from the second case of the master theorem:		So it follows from the second case of the master theorem:

	:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math>		:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math>

	Thus the given recurrence relation <math>T(n)</math> was in <math>\Theta(n \log n)</math>.		Thus the given recurrence relation <math>T(n)</math> was in <math>\Theta(n \log n)</math>.
Line 259:		Line 256:

	* [[Akra–Bazzi method]]		* [[Akra–Bazzi method]]
	* [[Asymptotic complexity]]		* [[Asymptotic complexity]]

	== Notes ==		== Notes ==