What is the divide-and-conquer paradigm?

Question

Accepted Answer

**Divide and conquer** solves a problem by (1) **dividing** it into smaller subproblems, (2) **conquering** each recursively, and (3) **combining** the results. Many efficient algorithms follow this template.

## The idea

If subproblems are independent and shrink quickly, the total work follows a recurrence you can analyze with the **Master Theorem**.

## Example: max element via divide and conquer

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## Classic examples

- **Merge sort / quicksort** — O(n log n) sorting.
- **Binary search** — O(log n).
- **Fast exponentiation, Karatsuba multiplication, closest pair.**

## Complexity

Often T(n) = a·T(n/b) + f(n); for merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## When to use / pitfalls

Use when a problem **splits cleanly** into independent subproblems. If subproblems **overlap**, prefer dynamic programming instead (to avoid recomputation). Recursion overhead and the combine step can dominate for small inputs.

## Why it matters

Divide and conquer is a reusable blueprint behind a huge fraction of efficient algorithms.

Recognizing the pattern lets you derive and analyze new algorithms quickly with recurrences.

It also maps naturally onto parallelism, since independent subproblems can run concurrently.