Divide and Conquer

Divide and conquer splits a problem into smaller instances of the same form, solves them independently, and combines their results.

Three obligations

1. Divide: define subproblems and show their sizes shrink.
2. Conquer: solve base cases and recurse on each subproblem.
3. Combine: construct the parent solution and account for its cost.

A common runtime recurrence is

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

where $a$ is the number of subproblems, each has size about $n/b$, and $f(n)$ covers partitioning and combination. The recursion tree, substitution, or the Master Theorem can solve suitable recurrences; irregular sizes and dependencies may require other methods.

Representative patterns

• Merge sort: two half-size sorts plus a linear merge, yielding $\Theta(n\log n)$.
• Quicksort: linear partition plus input-dependent subproblem sizes.
• Binary search: one half-size subproblem plus constant combine work.
• Closest pair and Karatsuba multiplication: the combine strategy is the key improvement over direct enumeration.

Simply splitting an algorithm does not improve it. The subproblem solutions and combine step must solve the original problem, and their recurrence must actually have a better bound.

Boundary with dynamic programming

Divide-and-conquer subproblems are usually independent. Heavy overlap causes repeated work and suggests memoization or dynamic programming. Conversely, both styles can use recursion; syntax does not determine the design technique.

Independent branches may run in parallel, but practical speedup is bounded by the critical path, combine work, scheduling, communication, and memory traffic.

A complete recurrence argument

For merge sort on eight elements, the subproblem sizes are one run of 8, two of 4, four of 2, then eight base cases of 1. Each of the three merge levels processes eight elements in total. In the simplified model $T(1)=1$, $T(n)=2T(n/2)+n$, this gives $T(2)=4$, $T(4)=12$, $T(8)=32$. These are model work units, not exact comparisons or elapsed time.

More generally, for $n=2^k$, every merge level costs $n$, there are $k$ such levels and $n$ leaves: $T(n)=n\log_2 n+n$. Correctness is a separate induction: size-zero/one runs are sorted; if the two smaller results are sorted, repeatedly taking the smaller front produces a sorted permutation of their union. Strictly smaller subproblems prove termination. Neither the recurrence alone nor termination alone proves that the output is correct.

When the Master Theorem applies

For $T(n)=aT(n/b)+f(n)$ with constants $a\geq1$, $b>1$, nonnegative combine cost and constant-cost base cases, compare $f(n)$ with $n^p$, where $p=\log_b a$. A common form gives:

• If $f(n)=O(n^{p-\varepsilon})$ for some $\varepsilon>0$, then $T(n)=\Theta(n^p)$.
• If $f(n)=\Theta(n^p)$, then $T(n)=\Theta(n^p\log n)$.
• If $f(n)=\Omega(n^{p+\varepsilon})$ for some $\varepsilon>0$ and $a f(n/b)\leq c f(n)$ eventually for some constant $c<1$, then $T(n)=\Theta(f(n))$.

These cases are sufficient, not exhaustive. Merge sort uses the middle case; binary search has $a=1$, $b=2$, $f(n)=\Theta(1)$ and gives $\Theta(\log n)$. It is also called decrease-and-conquer because only one smaller problem is solved. Quicksort with arbitrary pivot positions does not have fixed equal-size branches, so applying the theorem directly to its worst case is invalid. Independent branches enable parallelism but do not eliminate the combine cost.

Source

• MIT OpenCourseWare: Divide and Conquer

My reading · Opened notes are remembered in this browser.