Divide and Conquer

Introduction

Divide and conquer is an general algorithmic technique that solves a problem by breaking it into smaller instances of the same problem, solving those instances recursively, and combining their solutions into a solution for the original. A common example of this is mergesort: we split an array in half, sort each half recursively, and merge the two sorted halves back together in linear time. The result is an $O(n \log n)$ sorting algorithm that beats other $O(n^2)$ sorting approaches.

The reason this technique is so powerful is that the "combine" step is often much cheaper than solving the problem from scratch. When we can stitch subproblem solutions together efficiently, the savings compound across every level of the recursion, and an algorithm that looks quadratic collapses into something nearly linear. The art of designing a divide and conquer algorithm usually lies in figuring out what information each subproblem should return so that the combine step has everything it needs.

General Framework

Every divide and conquer algorithm follows the same three-step recipe:

1. Divide. Break the problem into one or more subproblems, each a smaller instance of the original. Typically we split the input into pieces of size $n / b$ for some constant $b > 1$; for example, mergesort splits the array into two halves, so $b = 2$.
2. Conquer. Solve each subproblem recursively. Once the subproblems are small enough (usually constant size), solve them directly as a base case.
3. Combine. Merge the solutions of the subproblems into a solution for the original problem.

To turn this recipe into a concrete algorithm, we need to specify three things: how we split the input, what the base case is, and how we combine subresults. To reason about correctness, we typically use induction on the size of the input. We show that the base case is handled correctly, then assume the recursive calls return correct solutions on their smaller inputs (the inductive hypothesis) and argue that the combine step produces a correct solution for the full input.

Runtime Analysis

Analyzing the runtime is where divide and conquer takes a bit more work than other algorithms. Most recurrence relations will take on the form

$$T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n).$$

where a problem of size $n$ will split into $a$ subproblems each of size $n / b$, and the divide and combine steps together take $f(n)$ time (e.g. $O(n), O(n^2)$ depending on the algorithm).

Unraveling Recurrences

We start analyzing the recurrence by recursing down one layer of our formula.

$$\begin{align*} T\left(\frac{n}{b}\right) &= a \cdot T\left(\frac{n}{b^2}\right) + f\left(\frac{n}{b}\right) \\ T(n) &= a \cdot \left(a \cdot T\left(\frac{n}{b^2}\right) + f\left(\frac{n}{b}\right) \right) + f(n). \end{align*}$$

The recursion bottoms out when the subproblem hits the base case, $\frac{n}{b^i} = 1$, i.e. at $i= \log_bn$. Substituting that in:

$$\begin{align*} T\left(n \right) &= \sum_{i = 0}^{\log_{b} n} a^i \cdot f\left( \frac{n}{b^i} \right) \end{align*}$$

Taking $f(n) = n^c$ for some $c > 0$, substitute this into each term of the sum:

$$\begin{align*} T\left(n \right) &= \sum_{i = 0}^{\log_{b} n} a^i \cdot \left( \frac{n}{b^i} \right)^c = \sum_{i = 0}^{\log_{b} n} a^i \cdot \frac{n^c}{b^{ic}} \end{align*}$$

This $n^c$ factor is constant across the sum, so we pull it out. We are left with a geometric series with ratio $r = \frac{a}{b^c}$:

$$\begin{align*} T\left(n \right) &= n^c \sum_{i = 0}^{\log_{b} n} \frac{a^i}{b^{ic}} = n^c \sum_{i = 0}^{\log_{b} n} \left( \frac{a}{b^{c}} \right)^i \end{align*}$$

Then, we consider the following 3 cases when evaluating this sum:

Case 1: $a > b^c$. In this case, $\frac{a}{b^c} > 1$, so the terms grow and the sum is dominated by its last term. Applying the finite geometric sum formula and dropping some of the constant terms:

$$\begin{align*} \sum_{i = 0}^{\log_{b} n} \left( \frac{a}{b^{c}} \right)^i = \dfrac{\left( \frac{a}{b^c} \right)^{\log_b{n} + 1} - 1}{\frac{a}{b^c} - 1} = O \left( \left( \frac{a}{b^c} \right)^{\log_b (n) + 1} \right) = O \left( \frac{a^{\log_b (n)}}{b^{\log_b (n)}} \right) = O \left( \frac{a^{\log_b (n)}}{n} \right) \end{align*}$$

We can use some math stuff to flip $a$ and $n$:

$$\begin{align*} a^{\log_b (n)} = \left(b^{\log_b (a)} \right)^{\log_b (n)} = \left(b^{\log_b (n)} \right)^{\log_b (a)} = n^{\log_b (a)} \\ \end{align*}$$

Then, we can get a final result for our summation as:

$$\begin{align*} O \left( \frac{a^{\log_b (n)}}{n} \right) = O \left( \frac{n^{\log_b (a)}}{n} \right) = O \left( n^{\log_b (a)} \right) \end{align*}$$

Case 2: $a < b^c$. Here, $\frac{a}{b^c} < 1$, so we can upper-bound this sum by the convergence of a geometric series:

$$\begin{align*} \sum_{i = 0}^{\log_{b} n} \left( \frac{a}{b^{c}} \right)^i < \sum_{i = 0}^{\infty} \left( \frac{a}{b^{c}} \right)^i = \dfrac{1}{1 - \frac{a}{b^c}} \end{align*}$$

Case 3: $a = b^c$. In this case, $\frac{a}{b^c} = 1$. Since $1^i = 1$ for all $i \in \mathbb R$, we have:

$$\begin{align*} \sum_{i = 0}^{\log_{b} n} \left( \frac{a}{b^{c}} \right)^i = \sum_{i = 0}^{\log_{b} n} \left(1 \right)^i = \log_b{(n)} + 1 \end{align*}$$

Master Theorem

Fast Fourier Transform

Practice

Problem 1. Consider a list of numbers $x_1, \dots, x_n$. We say that two numbers $x_i$ and $x_j$ from this list form an inversion if $i < j$ but $x_i > x_j$. For example, a list of numbers sorted in ascending order would have $0$ inversions, while a list of numbers sorted in descending order would have $0 + 1 + \dots + (n - 1) = n(n - 1)/2$ inversions (each pair of numbers form an inversion). Design a divide and conquer algorithm that runs in time $O(n \log n)$ that counts the number of inversions of a list of $n$ numbers. You may assume $n$ is a power of 2.

Hint 1

Let the goal of our divide and conquer be to find the number of inversions in a list of numbers $x_1, \dots, x_k$. What are our subproblems here (hint: split the list in half)?

Hint 2

If we split our list into subproblems $x_1, \dots, x_{k/2}$ and $x_{k/2 + 1}, \dots, x_n$, note that any inversion pair $(i, j)$ either has both indices in the left half, both indices in the right half or $i$ in the left half and $j$ in the right half. The first two cases are handled recursively, but how do you efficiently count the "split" inversions where $i \le k / 2 < j$? (hint: sorting may help)

Solution

Coming soon!

Problem 2. Assume a group of $n$ friends each independently decide to take a piece of candy from a bowl. Each friend has their own probability of taking a piece of candy; let $p_i$ be the probablity that the $i$th friend takes candy from the bowl (thus with probability $1 - p_i$, they don't take the candy). We want to know, for $k = 0, \dots, n$, the probability that exactly $k$ friends take candy. Note that the probability of all $n$ friends taking candy is $\prod_{i = 1}^n p_i$, while the probability that no one takes candy is $\prod_{i = 1}^n (1 - p_i)$. Give a divide and conquer algorithm to find the probabilities that exactly $k$ friends take candy from the bowl. You may assume that there is always enough candy in the bowl for everyone to take a piece if they choose to. Your algorithm should run in polynomial time, and you can assume $n$ is a power of 2.

Hint 1

Use Fast Fourier Transform. How can you represent these probabilities as a convolution or polynomial multiplication?

Hint 2

Consider a small example where $p_1 = 0.75$ and $p_2 = 0.6$. After finding the probability that we take $k = 0, 1, 2$ candies, create polynomials $q_1 = 0.75x + 0.25$ and $q_2 = 0.6x + 0.4$ and multiply them together. What do the coefficients of our new polynomial represent in this case?

Solution

Coming soon!