Divide & Conquer

Summary

Solved rank-finding by using medians of medians, then introduced a divide-and-conquer algorithm for integer multiplication: Karatsuba.

---

The input is a problem of size . We divide input into subproblems, each of size . We conquer each subproblem recursively, and then combine subproblem solutions to solve the original problem.

Rank Finding

The input is an unsorted array of distinct numbers and a rank . Output the smallest number, i.e. the unique with

For instance, to find the median, .

Example

. Median = 2, Max = 10, Min = -5.

Can we do better than ? Yes. We can do (solved in 1973).

One idea is to pick a pivot and partition into and . Comparing to tells us which side the answer lives on, so we only need to recurse into one of the two halves. Since each recursive call shrinks the problem, a good pivot choice (near the median) gives . This still could be bad if our pivot is far to the right or far to the left. In the worst case, we get

No improvement. If we could luckily get the median every time, we would have an solution.

Definition

For , we say is c-balanced if

Note

If we can find a c-balanced element in time, we can solve rank finding in time.

The solution is recursive. We divide into buckets, each of size . We compute each bucket’s median, which we can do in constant time. Then we compute the median of all the bucket medians and use that as the pivot. The rest of the algorithm is standard divide-and-conquer.

The tricky part is the time complexity of finding the median of medians.

Claims

1. Median of medians is -balanced.

2. The runtime is .

Proof

1. This is best illustrated in a picture. Notice that the colored elements on each side are at least which means picking the pivot as the median of medians yields a -balanced solution.
2. Finding the median of medians takes , since it is itself a rank-finding problem on the bucket medians. Then finding the rank takes , since the pivot is -balanced so we recurse on at most elements.

We will prove by induction that . Induction step: . To ensure this is at most , we need .

Integer Multiplication

We input two -bit numbers and . We want to output their product . The grade-school algorithm takes time. Kolmogorov conjectured that this was optimal. He was wrong; Karatsuba found a divide-and-conquer algorithm that is better.

Karatsuba Algorithm

Split each number in half: and . Expanding the product gives

which naively requires four multiplications of -bit numbers (, , , ), giving — no better than grade school.

Karatsuba’s trick is to notice that we already compute and , so we can get the cross term for free: . This replaces two recursive multiplications with one, bringing us down to three multiplications of size . So now we only need three recursive multiplications: , , and . We recover the cross term as . Then appending zeros to is just multiplying by , and appending zeros to is multiplying by , so we return .

The recurrence becomes .

Is this the fastest? IN 1971, Schönge-Strassen found . In 2007, it was brought down to , where is the number of times you must apply to before the result is . It grows absurdly slowly (e.g. ), so is is nearly constant.

Not to worry about , as in 2019 an solution was found.

Recitation

1. Divide & Conquer
   1. Divide, conquer, combine
2. Median Finding

We often see recurrences in the form

The Master Theorem is a general method for analyzing recurrence relations of the above form. It turns out that is important: it’s the recursion cost, while is the one-time cost. We need to see which dominates.

3. Is is polynomially greater, then it’s just We can also use substitution.

Example

We will use induction. . Let’s guess it’s , i.e. .