Main content
Divide and conquer algorithms
The two sorting algorithms we've seen so far, selection sort and insertion sort, have worst-case running times of
| Algorithm | Worst-case running time | Best-case running time | Average-case running time |
|---|---|---|---|
| Selection sort | |||
| Insertion sort | |||
| Merge sort | |||
| Quicksort |
Divide-and-conquer
Both merge sort and quicksort employ a common algorithmic paradigm based on recursion. This paradigm, divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem, and there must be a base case for subproblems. You should think of a divide-and-conquer algorithm as having three parts:
- Divide the problem into a number of subproblems that are smaller instances of the same problem.
- Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
- Combine the solutions to the subproblems into the solution for the original problem.
You can easily remember the steps of a divide-and-conquer algorithm as divide, conquer, combine. Here's how to view one step, assuming that each divide step creates two subproblems (though some divide-and-conquer algorithms create more than two):
If we expand out two more recursive steps, it looks like this:
Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls.
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
What is the connection/difference between recursive algorithms, divide and conquer and dynamic programming?(11 votes)
Why balancing is necessary in divide and conquer?(3 votes)
Here's the idea (I've somewhat simplified it):
Solving a divide and conquer problem will cost you:
cost/level * number of levels
If, each level, you break each sub problem into two equal sized chunks, then it will take log_2(n) levels before the sub problem size is broken into chunks of size 1.
However, if you break each of the the sub problems into one big chunk and one small chunk, then it can take almost n levels before the sub problems are broken into chunks of size 1.
So, dividing each of the sub problems evenly will cost you:
log_2(n) * cost/level
And, dividing each of the sub problems into a big chunk, and small chunk will cost you somewhere around:
n * cost/level (which is much worse)
So for something like quick sort (which using the idea of divide and conquer):
It costs n per level
When it divides the problem evenly into nearly halves, it runs in: O(n * log_2(n))
When it divides the problem into a big chunk and small chunk, it runs in: O(n*n) i.e. O(n^2)
Hope this makes sense(10 votes)
What type of problem can come in divide and conquer strategy?(5 votes)- 1. Give a divide and conquer algorithm to search an array for a given integer. a. The algorithm must solve the following problem: Input: A, an integer array and k an integer. Output: TRUE if there is an A[i] = k. b. Provide an explanation of how your algorithm works c. Formal pseudocode of the algorithm d. A proof that the algorithm is correct e. A symbolic runtime analysis of the algorithm(2 votes)
Divide and conquer search(array):
if array is single element:
if target found:
return true
else:
return false
return Divide and conquer search(left half of array) || Divide and conquer search(right half of array)
You search every element exactly once so it is O(n)(2 votes)
- Looking at the running time table, it would appear that merge sort is a bit more superior than quick sort. Would there be a reason to choose quick sort over merge sort (assuming you were familiar with both)?(1 vote)
- Posting here really about the(just prior to this page) stage 2 Challenge Solve hanoi recursively (no place to put questions on that page).
The questions asks the following:
Make a recursive function call to move the disks sitting on top of the bottom disk on the fromPeg to the spare peg, i.e. move (numDisks - 1) disks to the spare peg.
You can find the spare peg by using the getSparePeg function.
A call to hanoi.getSparePeg(peg1,peg2) returns the remaining peg that isn't peg1 or peg2.
The hint says this:
// recursive case:
var sparePeg = hanoi.getSparePeg(fromPeg, toPeg);
solveHanoi();
But despite all that, even though it only seems to ask for the solveHanoi() to be filled out with the parameters, it wont progress. Do I have to seperately declare the fromPeg, and toPeg, and assign them letters?
Below is a rough stab at the code:
var solveHanoi = function(numDisks, fromPeg, toPeg) {
if (numDisks===0)
{
return;
}
};
var fromPeg="A";
var toPeg="B";
var sparePeg = hanoi.getSparePeg(fromPeg,toPeg);
//solveHanoi(5, "A","B");
//Program.assertEqual(hanoi.isSolved("B"),true);(2 votes)
You are writing the recursive case code outside of the solveHanoi function. Try placing it inside the function.(0 votes)
- Design a heap construction algorithm by applying divide and conquer strategy
??(0 votes)- put data in heap (not in heap order yet) and call heapifyRecursive on top node
heapifyRecursive( node ) {
if ( node == null ) {
return;
}
//this is the divide and conquer step
heapifyRecursive( left child);
heapifyRecursive( right child );
//this step merges the results together into a valid heap
heapifyDown( node );
}(1 vote)
Alexander Malena-Is there a connection between dividing and conquer algorithms in terms of how they are both used?(0 votes)- Not understanding the code for base case for tower of hanoi problem. Please advise.(0 votes)
- As the number of disks is 0 , the function returns the zero value for the parameter refers to the number of disks(1 vote)
