Divide and Conquer

Split into subproblems, recurse, combine — then time it by comparing work against leaves.

The idea

Divide and conquer is a design paradigm that builds an algorithm out of smaller copies of itself, in three steps: divide the instance, conquer the pieces by recursion, combine their answers.

Algorithm.

Algorithm: Divide and Conquer (the scheme) Input: an instance of size n Output: a solution to the instance 1. if n is small enough, solve the instance outright and return the answer // base case 2. divide the instance into a subproblems, each of size n/b 3. conquer each subproblem by running this algorithm on it 4. combine the a sub-answers into an answer for the instance; return it

The paradigm also lets us compute the running time without tracing an execution. Let $f(n)$ be the cost of dividing and combining in one call. The total time obeys the recurrence $T(n) = a\,T(n/b) + f(n).$ Unfolding the recurrence produces a tree. The root does $f(n)$ work and has $a$ children of size $n/b$; those have $a$ children each of size $n/b^{2}$; after $\log_b n$ levels the sizes reach $1$. The bottom level therefore holds $a^{\log_b n} = n^{\log_b a}$ leaves, each doing constant work. The exponent $\log_b a$ measures how fast the subproblems multiply against how fast they shrink, and it governs the whole cost.

To read off the cost, compare $f(n)$ with $n^{\log_b a}$. If $f(n)$ grows more slowly, the work accumulates toward the bottom and the leaves dominate: $T(n) = \Theta(n^{\log_b a})$. If $f(n)$ grows faster, the top-level call dominates: $T(n) = \Theta(f(n))$. If the two match, every level costs the same, and the $\log_b n$ levels contribute an extra factor of $\log n$.

Ways to work on it

• Walkthrough. The divide/conquer/combine paradigm and merge sort's running time.
• Practice. Read off T(n) for a divide-and-conquer recurrence.
• Hardest. Derive and solve the recurrence for Karatsuba multiplication.

Not sure where to start? Take the ten-question placement test.