Overview

This chapter dives deep into the divide-and-conquer paradigm—splitting a problem into smaller subproblems, solving them recursively, and combining the results. It presents two major algorithmic applications (maximum subarray and matrix multiplication) and three methods for solving the recurrences that characterize divide-and-conquer running times: the substitution method, the recursion-tree method, and the master method.

Key Concepts

• Divide-and-conquer paradigm: Three steps at each level of recursion:

1. Divide the problem into smaller subproblems.

2. Conquer the subproblems by solving them recursively (or directly if small enough—the base case).

3. Combine the subproblem solutions into the overall solution.

• Recurrences: Equations or inequalities that describe a function in terms of its value on smaller inputs. They naturally characterize divide-and-conquer running times.
• Technicalities: Floors, ceilings, and boundary conditions are typically ignored in recurrence formulations because they don't affect the asymptotic solution (justified by Theorem 4.1).

Algorithms and Techniques

Maximum-Subarray Problem (Section 4.1)

• Problem: Given an array of numbers (some negative), find the contiguous subarray with the largest sum.

• Motivation: Modeled as a stock-trading problem—find the best time to buy and sell by transforming prices into daily changes.

• Brute-force: Check all Θ(n²) subarrays → Θ(n²) time.

• Divide-and-conquer solution:

• Divide at the midpoint.

• A maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint.

• FIND-MAX-CROSSING-SUBARRAY finds the best crossing subarray in Θ(n) time by extending left and right from the midpoint.

• FIND-MAXIMUM-SUBARRAY recursively solves left and right halves, finds the crossing subarray, and returns the best of the three.

• Recurrence: T(n) = 2T(n/2) + Θ(n), giving T(n) = Θ(n lg n).