Divide and Conquer

Divide and Conquer: divide, solve recursively, combine (Mergesort, Quicksort, classical median-of-medians ideas).

Complexity often expressed through recurrence relations (Master Theorem).

$$T(n)=aT(n/b)+f(n)$$

Where used

Merge/Quick, FFT pipelines, parallel aggregation, MapReduce concept. Break down, solve independently, combine.

Depth

Divide and Conquer breaks a problem into smaller instances, solves these recursively, and combines their results into an overall solution. A base case ends the division. The shape and balance of the subproblems determine the height and width of the recursion tree.

The runtime can often be expressed through a recurrence. With two half-sized subproblems and linear additional work, the pattern of Merge Sort emerges. If only one subproblem is pursued, as in binary search, a different recurrence arises.

Difficulty levels

1. Identify the division, base case, and combination.
2. Formulate a recurrence from the process.
3. Analyze the balance and additional work in the recursion tree.

Pitfalls

Not every recursion is Divide and Conquer. The subproblems should clearly be smaller and usually largely independent. Strongly overlapping subproblems indicate more suitable approaches such as memoization or dynamic programming.