Divide and conquer

Prerequisites

• Recursion and base cases.
• Merge sort, the textbook example.
• Logarithms: halving $n$ takes $\log_2 n$ steps.

The analogy

How it works

The three steps: Divide the problem into smaller subproblems of the same type; conquer each one recursively (tiny ones directly); combine their answers.

Start with the split tree by hand

Sort [4, 1, 3, 2] with the three steps. Predict, then open "Check".

Finish the picture: the same idea elsewhere

Try the three steps on two other problems.

• Maximum of [4, 1, 3, 2]. Predict the answers of the halves and the combine.
  Check

  max([4, 1]) = 4, max([3, 2]) = 3, combine: max(4, 3) = 4. Combining is one comparison.

• Binary search for 3 in [1, 2, 3, 4]. Predict how many subproblems are solved at each level.
  Check

  Only one: the half that can contain 3. That's why binary search is $O(\log n)$ instead of $O(n)$.

The rule in plain words

Write a base case small enough to solve directly. Otherwise divide the input, recurse on the parts, and combine the results.

The cost is set by three things: how many subproblems, how big each is, and how expensive the divide and combine steps are.

The code

Read this code after you have done the split tree by hand. It will make more sense.

int max_dc(int a[], int lo, int hi) {           /* maximum of a[lo..hi] */
    if (lo == hi) return a[lo];                 /* base case: one element */
    int mid = lo + (hi - lo) / 2;               /* divide */
    int l = max_dc(a, lo, mid);                 /* conquer the left half */
    int r = max_dc(a, mid + 1, hi);             /* conquer the right half */
    return l > r ? l : r;                       /* combine */
}

flowchart TD
  A{"is the problem small?"} -->|yes| B["solve it directly (base case)"]
  A -->|no| C["divide into subproblems"]
  C --> D["solve each subproblem recursively"]
  D --> E["combine the answers"]
          

How fast is it?

Draw the recursion tree. For merge sort there are $\log_2 n$ levels, and the combine steps on each level touch all $n$ elements once:

For max_dc, each combine is one comparison and there are $n - 1$ of them in total, so it is $O(n)$, no better than a simple loop.

Common mistakes

• Forgetting the base case, which recurses forever.
• Splitting into subproblems that are not smaller, e.g. mid = hi, which also never ends.
• Using divide and conquer when subproblems overlap; memoise them instead.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Divide and conquer is recursive because each subproblem is a smaller copy of the original.
• Merge sort is $O(n \log n)$ because it has $\log_2 n$ levels and $O(n)$ combine work per level.
• Binary search is $O(\log n)$ because it solves only one subproblem per level.
• A base case is essential because without it the splitting never stops.
• Overlapping subproblems call for dynamic programming because divide and conquer would recompute them.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is divide and conquer like counting a country's votes?
   Sample answer

   Each town counts its own votes, regions add up their towns, and the capital adds up the regions: split, solve the small parts, combine.

2. Walk through divide and conquer on [4, 1, 3, 2] with merge sort.
   Sample answer

   Split into [4, 1] and [3, 2], then into single numbers; merge into [1, 4] and [2, 3]; merge into [1, 2, 3, 4].

3. Why does max_dc stop when lo == hi?

   A good answer names the base case.

   Sample answer

   A one-element range is the base case: its maximum is that element, so there is nothing left to split.

4. So what is divide and conquer, in one sentence?
   Sample answer

   Solving a problem by splitting it into smaller independent subproblems of the same type, solving them recursively and combining the results.

5. Why is merge sort $O(n \log n)$ while max_dc is only $O(n)$?

   A good answer compares the combine steps.

   Sample answer

   Both have $\log_2 n$ levels, but merge sort's combine touches all $n$ elements per level, while max_dc's combine is a single comparison, $n - 1$ comparisons in total.

6. What do binary search, merge sort and Karatsuba cost?
   Sample answer

   $O(\log n)$, $O(n \log n)$ and $O(n^{1.585})$.

7. When is divide and conquer the wrong tool?
   Sample answer

   When subproblems overlap, as in naive Fibonacci; then memoising or dynamic programming avoids recomputation.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out Karatsuba and the inversion count. I'd keep the vote-counting analogy, the [4, 1, 3, 2] split tree, and "divide, conquer, combine; cost = levels × work per level".

External resources

• VisuAlgo: Sorting: watch merge sort and quick sort divide and combine.
• GeeksforGeeks: Divide and conquer: the paradigm with classic examples.
• Wikipedia: Divide-and-conquer algorithm: history and examples.
• MIT OCW 6.006: lectures on recursive algorithms.

Videos

• YouTube search: divide and conquer explained: pick an overview with examples.