Divide and Conquer (Master Theorem)

Divide and Conquer: an Intro #

Sometimes, especially for recursive algorithms, we can write a runtime as a recurrence relation: that is, part of a function’s runtime definition is the function itself with a smaller problem size.

This applies directly to a method called divide and conquer, which goes something like this:

• We’re given some input $x$ and are trying to evaluate a function $A(x)$.
• We can split $x$ into smaller parts $x_1, x_2, \cdots x_a$.
• We can then find the output of each individual part $A(x_1), A(x_2), \cdots A(x_a)$.
• Sum up all of these outputs to get the original desired value $A(x)$.

Take this example (Karatsuba Multiplication): $T(n) = 3T(n/2) + cn$

The General Form #

$a$, $b$ and $c$ are constants and $T(n)$ is the total amount of work that must be done for an input size of $n$.

Master Theorem for Recurrences #

Root Heavy

Balanced

Leaf Heavy

Proof:

Here’s a chart of how the problem evolves down the layers. At the end, we will need to calculate $T(1)$, which is assumed (without loss of generality) to be a constant work per problem $c$.

If we sum up all of the total work per layer, we get the expression:

There are three cases (as shown above). We can split them now to evaluate this sum.

Root Heavy: $a/b^d < 1$, so $d > log_b(a)$.

Recall that $1 + p + p^2 + \cdots + p^k = \frac{p^{k+1}-1}{p-1}$ by the geometric series formula.

So:

which simplifies to $O(n^d)$ since the geometric series converges to a constant when $a/b^d < 1$.

Balanced: $a/b^d = 1$.

This means that the work for each layer must be $1$ because $\frac{a}{b^d} = \frac{a}{b^{log_b(a)}} = \frac{a}{a}$.

Since there are $log_b(n)$ layers, the total work done must be $c \cdot n^d (log_b(n)) \implies O(n^d log_b(n))$.