Why do divide and conquer algorithms often run faster than brute force?

Question

Why do divide and conquer algorithms often run faster than brute force? For example, to find closest pair of points. I know you can show me the mathematical proof. But intuitively, why does this happen? Magic?

Theoretically, is it true that "divide and conquer is always better than brute force"? If it is not, is there any counterexample?

Lecialecithin

To share a cake into 16 pieces, the first solution is to try to cut 1/16 of the cake and so on... difficult. Another solution is to cut the cake in 2, then in 2 again, then each of the 1/4 in 2, and each of the 1/8 in 2. – Putrescible

Answer 1

For your first question, the intuition behind divide-and-conquer is that in many problems the amount of work that has to be done is based on some combinatorial property of the input that scales more than linearly.

For example, in the closest pair of points problem, the runtime of the brute-force answer is determined by the fact that you have to look at all O(n²) possible pairs of points.

If you take something that grows quadratically and cut it into two pieces, each of which is half the size as before, it takes one quarter of the initial time to solve the problem in each half, so solving the problem in both halves takes time roughly one half the time required for the brute force solution. Cutting it into four pieces would take one fourth of the time, cutting it into eight pieces one eighth the time, etc.

The recursive version ends up being faster in this case because at each step, we avoid doing a lot of work from dealing with pairs of elements by ensuring that there aren't too many pairs that we actually need to check. Most algorithms that have a divide and conquer solution end up being faster for a similar reason.

For your second question, no, divide and conquer algorithms are not necessarily faster than brute-force algorithms. Consider the problem of finding the maximum value in an array. The brute-force algorithm takes O(n) time and uses O(1) space as it does a linear scan over the data. The divide-and-conquer algorithm is given here:

• If the array has just one element, that's the maximum.
• Otherwise:
  • Cut the array in half.
  • Find the maximum in each half.
  • Compute the maximum of these two values.

This takes time O(n) as well, but uses O(log n) memory for the stack space. It's actually worse than the simple linear algorithm.

As another example, the maximum single-sell profit problem has a divide-and-conquer solution, but the optimized dynamic programming solution is faster in both time and memory.

Hope this helps!

Eer

Answer 2

I recommend you read through the chapter 5 of Algorithm Design, it explains divide-and-conquer very well.

Intuitively, for a problem, if you can divide it into two sub-problems with the same pattern as the origin one, and the time complexity to merge the results of the two sub-problems into the final result is somehow small, then it's faster than solve the orignal complete problem by brute-force.

As said in Algorithm Design, you actually cannot gain too much from divide-and-conquer in terms of time, general you can only reduce time complexity from higher polynomial to lower polynomial(e.g. from O(n^3) to O(n^2)), but hardly from exponential to polynomial(e.g. from O(2^n) to O(n^3)).

I think the most you can gain from divide-and-conquer is the mindset for problem solving. It's always a good attempt to break the original big problem down to smaller and easier sub-problems. Even if you don't get a better running time, it still helps you think through the problem.

Hollow