Divide-and-conquer algorithm - Revision history

Tea2min: /* See also */ Skip redirect in piped link.

2025-05-14T09:50:22Z

Polygnotus: /* Algorithm efficiency */ clean up, replaced: parital → partial

2025-03-04T03:47:10Z

Algorithm efficiency: clean up, replaced: parital → partial

← Previous revision		Revision as of 03:47, 4 March 2025
Line 43:		Line 43:
	* if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>		* if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>

	If, instead, the work of splitting the problem and combining the ~~parital~~ solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>		If, instead, the work of splitting the problem and combining the partial solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>

	=== Parallelism ===		=== Parallelism ===

NOTmaneless: Added links

2025-02-13T20:13:48Z

Added links

← Previous revision		Revision as of 20:13, 13 February 2025
Line 4:		Line 4:
	The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as [[sorting algorithm\|sorting]] (e.g., [[quicksort]], [[merge sort]]), [[multiplication algorithm\|multiplying large numbers]] (e.g., the [[Karatsuba algorithm]]), finding the [[Closest pair of points problem\|closest pair of points]], [[syntactic analysis]] (e.g., [[top-down parser]]s), and computing the [[discrete Fourier transform]] ([[fast Fourier transform\|FFT]]).<ref>{{cite book \|last1=Blahut \|first1=Richard \|author1-link=Richard Blahut \|title=Fast Algorithms for Signal Processing \|date=14 May 2014 \|publisher=Cambridge University Press \|isbn=978-0-511-77637-3 \|pages=139–143}}</ref>		The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as [[sorting algorithm\|sorting]] (e.g., [[quicksort]], [[merge sort]]), [[multiplication algorithm\|multiplying large numbers]] (e.g., the [[Karatsuba algorithm]]), finding the [[Closest pair of points problem\|closest pair of points]], [[syntactic analysis]] (e.g., [[top-down parser]]s), and computing the [[discrete Fourier transform]] ([[fast Fourier transform\|FFT]]).<ref>{{cite book \|last1=Blahut \|first1=Richard \|author1-link=Richard Blahut \|title=Fast Algorithms for Signal Processing \|date=14 May 2014 \|publisher=Cambridge University Press \|isbn=978-0-511-77637-3 \|pages=139–143}}</ref>

	Designing efficient divide-and-conquer algorithms can be difficult. As in [[mathematical induction]], it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving [[recurrence relation]]s.		Designing efficient divide-and-conquer algorithms can be difficult. As in [[mathematical induction]], it is often necessary to generalize the problem to make it amenable to a [[Recursion (computer science)\|recursive]] solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving [[recurrence relation]]s.

	== Divide and conquer ==		== Divide and conquer ==
	[[File:Merge sort algorithm diagram.svg\|thumb\|Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. ''Upper half:'' splitting into sublists; ''mid:'' a one-element list is trivially sorted; ''lower half:'' composing sorted sublists.]]		[[File:Merge sort algorithm diagram.svg\|thumb\|Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. ''Upper half:'' splitting into sublists; ''mid:'' a one-element list is trivially sorted; ''lower half:'' composing sorted sublists.]]
	The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.		The divide-and-conquer [[Programming paradigm\|paradigm]] is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.
	For example, to sort a given list of ''n'' [[Natural number\|natural numbers]], split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.		For example, to sort a given list of ''n'' [[Natural number\|natural numbers]], split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.

Kku: /* See also */ annlink

2025-02-11T09:03:02Z

Arjayay: Duplicate word removed

2025-01-30T21:09:27Z

Duplicate word removed

← Previous revision		Revision as of 21:09, 30 January 2025
Line 41:		Line 41:

	* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.		* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.
	* if the number of subproblems is exactly one, ~~then~~ then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>		* if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>

	If, instead, the work of splitting the problem and combining the parital solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>		If, instead, the work of splitting the problem and combining the parital solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>

Thomas Meng: /* Algorithm efficiency */ added new class of runtime for D&C algorithms

2025-01-29T04:43:17Z

Algorithm efficiency: added new class of runtime for D&C algorithms

← Previous revision		Revision as of 04:43, 29 January 2025
Line 42:		Line 42:
	* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.		* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.
	* if the number of subproblems is exactly one, then then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>		* if the number of subproblems is exactly one, then then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>

			If, instead, the work of splitting the problem and combining the parital solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>

	=== Parallelism ===		=== Parallelism ===

Thomas Meng: /* Algorithm efficiency */ copy edit for clarity

2025-01-29T04:38:26Z

Algorithm efficiency: copy edit for clarity

← Previous revision		Revision as of 04:38, 29 January 2025
Line 38:		Line 38:
	In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>\frac{n}{p}</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.		In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>\frac{n}{p}</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.

	For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>\frac{n}{2}</math>, the running times are as follows:		For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>\frac{n}{2}</math>. Then, the running times are as follows:

	* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.		* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.

Thomas Meng: /* Algorithm efficiency */ reformatted

2025-01-29T04:37:34Z

Algorithm efficiency: reformatted

← Previous revision		Revision as of 04:37, 29 January 2025
Line 36:		Line 36:
	The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to [[Karatsuba algorithm\|Karatsuba]]'s fast multiplication method, the quicksort and mergesort algorithms, the [[Strassen algorithm]] for [[matrix multiplication]], and fast Fourier transforms.		The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to [[Karatsuba algorithm\|Karatsuba]]'s fast multiplication method, the quicksort and mergesort algorithms, the [[Strassen algorithm]] for [[matrix multiplication]], and fast Fourier transforms.

	In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>n/p</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.		In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>\frac{n}{p}</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.

	For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>n/2</math>, the running times are as follows:		For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>\frac{n}{2}</math>, the running times are as follows:

	* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.		* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.

Thomas Meng: /* Algorithm efficiency */ added citation

2025-01-29T04:35:45Z

Algorithm efficiency: added citation

← Previous revision		Revision as of 04:35, 29 January 2025
Line 41:		Line 41:

	* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.		* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.
	* if the number of subproblems is exactly one, then then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.		* if the number of subproblems is exactly one, then then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|pages=214-220 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>

	=== Parallelism ===		=== Parallelism ===

Thomas Meng: /* Algorithm efficiency */ added other generalized classes' runtimes

2025-01-29T04:32:03Z

Algorithm efficiency: added other generalized classes' runtimes

← Previous revision		Revision as of 04:32, 29 January 2025
Line 37:		Line 37:

	In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>n/p</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.		In all these examples, the D&C approach led to an improvement in the [[asymptotic complexity\|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)\|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>n/p</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.

			For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>n/2</math>, the running times are as follows:

			* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.
			* if the number of subproblems is exactly one, then then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.

	=== Parallelism ===		=== Parallelism ===

← Previous revision		Revision as of 09:50, 14 May 2025
Line 90:		Line 90:
	* {{annotated link\|Akra–Bazzi method}}		* {{annotated link\|Akra–Bazzi method}}
	* {{annotated link\|Decomposable aggregation function}}		* {{annotated link\|Decomposable aggregation function}}
	* {{annotated link\|Divide and ~~rule~~\|"Divide and conquer"}}		* {{annotated link\|Divide and conquer\|"Divide and conquer"}}
	* {{annotated link\|Fork–join model}}		* {{annotated link\|Fork–join model}}
	* {{annotated link\|Master theorem (analysis of algorithms)}}		* {{annotated link\|Master theorem (analysis of algorithms)}}

← Previous revision		Revision as of 09:03, 11 February 2025
Line 88:		Line 88:

	{{Commons category\|Divide-and-conquer algorithms}}		{{Commons category\|Divide-and-conquer algorithms}}
	* [[Akra–Bazzi method]]		* {{annotated link\|Akra–Bazzi method}}
	* [[Decomposable aggregation function]]		* {{annotated link\|Decomposable aggregation function}}
	* [[Divide and rule\|"Divide and conquer"]]		* {{annotated link\|Divide and rule\|"Divide and conquer"}}
	* [[Fork–join model]]		* {{annotated link\|Fork–join model}}
	* [[Master theorem (analysis of algorithms)]]		* {{annotated link\|Master theorem (analysis of algorithms)}}
	* [[Mathematical induction]]		* {{annotated link\|Mathematical induction}}
	* [[MapReduce]]		* {{annotated link\|MapReduce}}
	* [[Heuristic (computer science)]]		* {{annotated link\|Heuristic (computer science)}}

	== References ==		== References ==