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 \Theta, left parenthesis, n, squared, right parenthesis. When the size of the input array is large, these algorithms can take a long time to run. In this tutorial and the next one, we'll see two other sorting algorithms, merge sort and quicksort, whose running times are better. In particular, merge sort runs in \Theta, left parenthesis, n, \lg, n, right parenthesis time in all cases, and quicksort runs in \Theta, left parenthesis, n, \lg, n, right parenthesis time in the best case and on average, though its worst-case running time is \Theta, left parenthesis, n, squared, right parenthesis. Here's a table of these four sorting algorithms and their running times:

Algorithm | Worst-case running time | Best-case running time | Average-case running time |
---|---|---|---|

Selection sort | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |

Insertion sort | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |

Merge sort | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |

Quicksort | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |

### 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?(2 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(9 votes)

- What type of problem can come in divide and conquer strategy?(4 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)
- 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)(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)