Chapter 4: Divide-and-Conquer: Recurrences and Matrix Multiplication

The strategy follows three steps: divide the problem into subproblems, conquer them recursively, and combine their solutions, with floors and ceilings generally ignorable when computing asymptotic bounds. Matrix multiplication serves as the central case study: the standard divide-and-conquer approach yields the recurrence T(n) = 8T(n/2) + Θ(1), solving to Θ(n³), while Strassen's algorithm cleverly reduces the number of recursive multiplications from eight to seven — trading costly multiplications for cheaper additions — giving T(n) = 7T(n/2) + Θ(n²), which solves to Θ(n^2.81). The chapter then presents four techniques for solving recurrences: the substitution method, where a solution is guessed and verified by induction; the recursion tree method, which visualizes costs level by level to generate an informed guess, particularly useful for unbalanced splits like T(n) = T(n/3) + T(2n/3) + Θ(n); the master method, a standardized formula for recurrences of the form T(n) = aT(n/b) + f(n) that classifies the solution by comparing f(n) to the watershed function n^(log_b a) across three cases; and the Akra-Bazzi method, a more general approach for recurrences with differing subproblem sizes where the master method falls short, solving by finding an exponent p such that the weighted sum of subproblem ratios equals one.