# Divide-and-Conquer Reasoning

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/divide-and-conquer-reasoning

## Split, Solve, Combine

**Divide-and-conquer** turns slow algorithms fast using a three-step pattern: **divide** a problem into smaller subproblems, **conquer** them recursively, and **combine** their answers.

| Step | Description |
| --- | --- |
| **Divide** | Split input into smaller subproblems of the same kind |
| **Conquer** | Recursively solve subproblems until trivially small |
| **Combine** | Merge subproblem solutions into the final answer |

Merge sort is the model example: split a list, sort each half, and merge them. Binary search is a degenerate form that discards one half.

Efficiency comes from shrinking problem size. The cost is captured by a **recurrence** like $T(n) = 2T(n/2) + O(n)$, meaning two half-size subproblems plus linear work, solving to $O(n \log n)$. The **Master Theorem** acts as a shortcut to solve these.

## When It Works & Pitfalls

Divide-and-conquer succeeds when a problem **decomposes** into independent subproblems and their solutions **combine** cheaply, turning quadratic brute force into $O(n \log n)$.

| Feature | Requirement for Success |
| --- | --- |
| **Decomposition** | Subproblems must be fully independent |
| **Combination** | Combining answers must be cheap ($O(n)$ or less) |

> **Common pitfall:** Applying divide-and-conquer when the **combine** step is expensive, or when subproblems **overlap** and repeat work exponentially.

If subproblems overlap, plain divide-and-conquer fails. That is the exact signal that **dynamic programming**, which stores and reuses subproblem answers, is the correct tool.

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Merge sort and binary search are both divide-and-conquer, yet one is O(n log n) and the other O(log n). Why does the same strategy give such different costs?

A. Because merge sort recurses into both halves and merges O(n) per level.
B. Because binary search operates on sorted data, which is inherently faster to process.
C. Because merge sort divides into more than two parts, adding to its cost.
D. Because binary search is not really divide-and-conquer, only appearing to be.

**Answer:** A. Because merge sort recurses into both halves and merges O(n) per level.

**Why:** Both halve the problem, so both have about log n levels; what differs is the work per level. Binary search discards half and does constant work; merge sort recurses into both halves and touches every element merging, giving O(n) per level. That is what the Master Theorem formalises — how many subproblems, how much smaller, how much combining — and it lets you predict a design change.

Page: https://tryals.app/practice/computer-science-i/divide-and-conquer-reasoning/merge-sort-and-binary-search-are-both-divide-and-conquer-yet-one-is

### 2. Order how merge sort applies divide-and-conquer to a list.

**Answer:**

1. Split the list into two halves
2. Recursively sort the left half
3. Recursively sort the right half
4. Merge the two sorted halves into one

**Why:** Split, sort each half, then merge. The merge is cheap (linear), which is exactly the condition that makes divide-and-conquer pay off here.

Page: https://tryals.app/practice/computer-science-i/divide-and-conquer-reasoning/order-how-merge-sort-applies-divide-and-conquer-to-a-list

### 3. Merge sort guarantees O(n log n) and quicksort is usually preferred anyway. What is quicksort buying, and what is it risking?

A. Buying stability at the cost of extra memory
B. Buying a better asymptotic bound at the cost of stability
C. Buying nothing, quicksort is preferred only by convention
D. A smaller constant and in-place operation, at the risk of O(n²)

**Answer:** D. A smaller constant and in-place operation, at the risk of O(n²)

**Why:** Quicksort partitions in place with excellent cache behaviour, where merge sort allocates a second array, a real cost at scale. The price is a quadratic worst case on sorted input with a naive pivot, mitigated by randomised or median-of-three pivots and by falling back to heapsort, which is what introsort does.

Page: https://tryals.app/practice/computer-science-i/divide-and-conquer-reasoning/merge-sort-guarantees-o-n-log-n-and-quicksort-is-usually-preferred

### 4. Select every condition under which plain divide-and-conquer is the right tool.

A. Each subproblem is a smaller version of the original
B. The combine step is expensive
C. The subproblem solutions combine cheaply
D. The subproblems overlap and are solved repeatedly
E. The problem splits into independent subproblems of the same kind

**Answer:** A. Each subproblem is a smaller version of the original; C. The subproblem solutions combine cheaply; E. The problem splits into independent subproblems of the same kind

**Why:** Divide-and-conquer wants independent, same-type, smaller subproblems that combine cheaply. Overlapping subproblems call for dynamic programming instead, and an expensive combine kills the speedup.

Page: https://tryals.app/practice/computer-science-i/divide-and-conquer-reasoning/select-every-condition-under-which-plain-divide-and-conquer-is-the