Advanced Algorithms · Lecture Notes
Chapter 1: Divide and Conquer
Solving a large problem head-on is usually hard. Half of the same problem is easier, and a quarter is easier still. At some point the problem becomes so small that its solution is obvious. Divide and conquer builds on this observation: split the problem into smaller pieces of the same kind, solve the pieces by the same method, and combine their solutions to answer the original question. Several algorithms you already know from sorting and searching fit this pattern. These notes first present the steps of the approach, its general template, and the way a recurrence relation gives the running time. They then take a brief paradigm-level look at the familiar algorithms. Most of the weight falls on four new algorithms: Quickhull for the convex hull, the strip method for the closest pair of points, Karatsuba integer multiplication, and Strassen matrix multiplication. For each algorithm the notes give code, a step-by-step trace, and a cost analysis.
Learning outcomes
- Paradigm
- Describe the steps of divide and conquer, and decide whether a problem suits the approach, in particular by checking whether its subproblems are independent or overlapping.
- Analysis
- Set up the recurrence of a divide-and-conquer algorithm; solve it with the master theorem or a recursion tree; recognize the cases where the master theorem does not apply.
- Geometric algorithms
- Find the convex hull with Quickhull and the closest pair of points with the strip method, step by step; compute the orientation test with integer multiplication alone; justify why at most seven comparisons per strip point suffice.
- Fast multiplication
- Show how Karatsuba (integer) and Strassen (matrix) multiplication reduce the running time by removing one recursive call; run both algorithms by hand on small examples.
1.1The divide-and-conquer paradigm
Designing an algorithm involves two things: the problem itself and the general strategy used to solve it. Patterns at the level of strategy are called paradigms. Brute force, the greedy approach, dynamic programming, and backtracking are such patterns. Divide and conquer is one of the oldest and most efficient of them. The name comes from a military maxim: if a large army cannot be defeated as a whole, split it into small units and defeat the units one at a time. In algorithms the "army" is the large problem and the "units" are its smaller copies.
1.1.1Divide, break down, conquer, combine
Divide and conquer is an algorithm design approach that splits a problem into smaller, mutually independent subproblems of the same kind. The subproblems are solved recursively by the same method, and their solutions are combined to build the solution of the original problem. Splitting stops when a subproblem is small enough to be solved directly; this situation is the base case.
The approach is usually described in four steps. Most textbooks list only three (divide, conquer, combine). The four-step description additionally stresses that splitting is not done once but repeatedly, until the base case is reached:
- Divide: The complex problem is split into smaller, manageable subproblems. For example, an array of n elements is split into two halves of n/2 elements.
- Break down: The subproblems keep being split until they are small enough to solve directly. Recursion provides this repetition: the same function is applied to the subproblem, and that function splits its own input in turn.
- Conquer: Each subproblem is solved separately. Base-case subproblems are solved directly; the others are solved by a recursive call.
- Combine: The solutions of the subproblems are combined to build the solution of the original problem.
Figure 1.1 shows this flow as a tree. The root of the tree is the original problem. Each internal node is a subproblem, and its children are the pieces it is split into. The leaves are base cases. The algorithm descends by splitting from the top and climbs back by combining from the bottom. In a program, the counterpart of this tree is the recursion tree: each node is a function call.
For the approach to work, the subproblems must have two properties. First, a subproblem is of the same kind as the original problem; it is merely smaller. Sorting an array is the same kind of task as sorting half of it. That is why the same function can call itself, and no separate "sort a half-array" function is needed. Second, the subproblems are independent of one another. Sorting the left half needs no information from sorting the right half. If this independence fails, that is, if the subproblems share common sub-subproblems, the same work is done over and over. The recursive Fibonacci computation is the best-known example.
1.1.2Why divide and conquer?
At first glance divide and conquer looks like merely a way of organizing work: split the job into pieces and do the pieces one by one. The real strength of the approach, however, is that on suitable problems it lowers the running time by an order of magnitude. Almost all of the algorithms discussed in these notes are asymptotically faster than the naive method for the same problem. Examples: O(n log n) instead of O(n2) for sorting, O(log n) instead of O(n) for searching a sorted array, and about O(n1.585) instead of O(n2) for integer multiplication.
The approach has other benefits as well:
- Clarity and reuse. A complex problem is easier to understand once it is split into small, manageable pieces. The method for solving subproblems is the same function at every level, so the code stays short and is reused at every level.
- Parallelism. Because the subproblems are independent, they can be solved at the same time on different processor cores. Sorting the left and right halves do not wait for each other.
- Memory locality. As subproblems shrink, they fit in the cache. A small subarray is loaded into the cache once and all the work on it finishes there. On large data this gives a visible speedup.
- Easy correctness proofs. The recursive structure makes it natural to prove correctness by induction: if the base case is correct and the combine step builds a correct solution from correct subsolutions, the algorithm is correct.
The costs of the approach should also be known:
- Recursion overhead. Every call opens a frame on the call stack, which costs time and memory. Some algorithms also need extra memory; merge sort, for example, uses an O(n) auxiliary array.
- Overlapping subproblems. If the subproblems are not independent, the same work is repeated and the running time can become exponential.
- Constant factors on small inputs. The asymptotic gain shows up at large n. At small n, the overhead of splitting, combining, and calling dominates. In practice a cutoff is therefore chosen, and once a subproblem falls below it, a simple method takes over. Karatsuba and Strassen implementations work this way.
Divide and conquer is used in many areas. Sorting and searching, computational geometry, and big-number and matrix arithmetic come first. The fast Fourier transform and game-tree search follow the same pattern.
1.1.3The general template
All divide-and-conquer algorithms follow the same skeleton. The Java code below writes this skeleton independent of any particular problem. The types Problem and Result and the methods split(), solveDirectly(), and combine() take on a different meaning in each algorithm.
Result divideAndConquer(Problem p) {
if (p.size() <= CUTOFF)
return solveDirectly(p); // base case
Problem[] parts = split(p); // a subproblems, size n/b
Result[] sols = new Result[parts.length];
for (int i = 0; i < parts.length; i++)
sols[i] = divideAndConquer(parts[i]); // conquer: recursion
return combine(sols); // combine
}The lines of the template match the steps of the paradigm one to one:
if (p.size() <= CUTOFF) return solveDirectly(p);is the base case. If the problem is no larger than the cutoff, splitting stops and the problem is solved directly. The cutoff is often 1: an array of one element is already sorted, and the maximum of one element is the element itself. A larger cutoff can also be chosen; in the closest pair of points it is 3.Problem[] parts = split(p);is the divide step. The problem is split into a subproblems, each of size about n/b.- The
forloop is the conquer step. For each subproblem the template itself is called. The break-down step is not a separate line; it happens inside this recursive call, when the subproblem is split again. return combine(sols);is the combine step. The subsolutions are turned into the final solution.
The running time of the template can be read off the same structure. Let T(n) be the time to solve a problem of size n. The algorithm solves a subproblems of size n/b recursively, and their total time is a · T(n/b). The time spent on splitting and combining is written f(n). This gives
T(n) = a · T(n/b) + f(n)
In this recurrence a is the number of subproblems, n/b is the subproblem size, and f(n) is the cost of splitting and combining. The recurrence summarizes the cost of a divide-and-conquer algorithm in three numbers. The ways to speed an algorithm up can be read off these same three numbers:
- Without a base case, the recursion never ends. The recurrence holds only for large n; for small n, T(n) is a constant. If the base case is forgotten, the program recurses forever and stops with a
StackOverflowError. - The split must be balanced. A split of the form n/2 + n/2 is good: the problem halves at every level, and the base case is reached after about log2 n levels. A split of the form 1 + (n − 1) is bad: the problem shrinks by only one element per level, and n levels are needed.
- The speedup most often comes from reducing a or shrinking f(n). The entire gain of Karatsuba and Strassen comes from reducing a by one. Lowering the combine cost from O(n log n) to O(n) is likewise decisive in the closest pair of points.
1.1.4Applying the template: the maximum element
To see the template on a concrete example, we choose a very simple problem: finding the maximum element of an array. A single loop also solves this problem, and divide and conquer does not shorten the running time here. The purpose of the example is to show what each part of the template looks like in code.
Divide and conquer sets the problem up as follows. The maximum of the array is the larger of the maximum of the left half and the maximum of the right half. This sentence reduces the problem to two smaller problems of the same kind. In a range of one element, the maximum is that element itself; this is the base case.
int findMax(int[] a, int lo, int hi) {
if (lo == hi) return a[lo]; // base
int mid = (lo + hi) / 2;
int left = findMax(a, lo, mid);
int right = findMax(a, mid + 1, hi);
return Math.max(left, right); // combine
}The method works on the range a[lo..hi] of the array. For the whole array one calls findMax(a, 0, n − 1). The lines do the following:
if (lo == hi) return a[lo];is the base case. The range holds one element, and that element is the maximum.int mid = (lo + hi) / 2;is the divide step. The range is split in the middle:[lo..mid]and[mid+1..hi]. Because integer division rounds down, the left half gets one extra element when the number of elements is odd.- The two recursive calls are the conquer step:
leftis the maximum of the left half andrightis the maximum of the right half. return Math.max(left, right);is the combine step and is a single comparison.
Splitting creates no new array; it only computes two indices. Splitting and combining together therefore take constant time: f(n) = O(1). The recurrence is T(n) = 2T(n/2) + O(1), and its solution is Θ(n).
1.1.5Code trace: findMax(a, 0, 4)
In the trace the array is a = [5, 2, 9, 4, 7] and the call is findMax(a, 0, 4). The range holds five elements. The middle index is (0 + 4)/2 = 2, so the left half is [0..2] and the right half is [3..4]. The left half gets three elements and the right half two. Table 1.1 gives the order of the calls and the value each call returns.
| Step | Event | Call stack | Return |
|---|---|---|---|
| 1 | (0, 4): mid = 2, left half [0..2] first | (0,4) | — |
| 2 | (0, 2): mid = 1, first [0..1], then [2..2] | (0,4), (0,2) | — |
| 3 | (0, 1): mid = 0, first [0..0], then [1..1] | (0,4), (0,2), (0,1) | — |
| 4 | (0, 0): single element, base case | …, (0,1), (0,0) | 5 |
| 5 | (1, 1): single element, base case | …, (0,1), (1,1) | 2 |
| 6 | (0, 1): left = 5, right = 2 → max | (0,4), (0,2), (0,1) | 5 |
| 7 | (2, 2): single element, base case | (0,4), (0,2), (2,2) | 9 |
| 8 | (0, 2): left = 5, right = 9 → max | (0,4), (0,2) | 9 |
| 9 | (3, 4): mid = 3, first [3..3], then [4..4] | (0,4), (3,4) | — |
| 10 | (3, 3): single element, base case | (0,4), (3,4), (3,3) | 4 |
| 11 | (4, 4): single element, base case | (0,4), (3,4), (4,4) | 7 |
| 12 | (3, 4): left = 4, right = 7 → max | (0,4), (3,4) | 7 |
| 13 | (0, 4): left = 9, right = 7 → max | (0,4) | 9 |
findMax(a, 0, 4). Each node is a lo..hi range; the number beside the arrow is the value that call returns. The five leaves are base cases; each of the four internal nodes makes one comparison.The order of the calls in the trace deserves attention. A call does not move on to the right half until the work on the left half is completely finished. At step 3 the call (0, 1) starts; at steps 4 and 5 it solves two leaves, and only at step 6 does it return its result. The right half (3, 4) does not start at all until step 9. This order is a depth-first traversal of the recursion tree. The call stack never holds more frames than the tree has levels; here there are at most four frames ((0,4), (0,2), (0,1), and one leaf).
The result is 9. The total number of calls is 9: 5 leaves and 4 internal nodes. The number of comparisons equals the number of internal nodes, that is, 4. In general, for an array of n elements the recursion tree has n leaves. Since every internal node has exactly two children, the number of internal nodes is n − 1. The algorithm makes n − 1 comparisons and 2n − 1 calls.
A simple loop also finds the maximum with n − 1 comparisons by scanning the array from start to end. Divide and conquer has not reduced the number of comparisons, and it has even added call overhead. What, then, is the benefit of this version? The answer is parallelism. The two halves are independent and can be solved at the same time. With an unlimited number of processors, each level of the tree finishes in one step. Since the height of the tree is ⌈log2 n⌉, the result is found in O(log n) parallel steps. In the loop version each comparison waits for the result of the previous one, and this chain cannot be shortened.
Believing that divide and conquer shortens the running time on every problem. In the maximum-element problem both halves must be examined in full; no element can be skipped. The total work therefore cannot drop below n. The gain appears in three situations. One of the subproblems can be discarded (binary search). The number of subproblems can be reduced (Karatsuba, Strassen). Or the combine step can be made cheaper than the naive method (merge sort, closest pair of points).
1.1.6Correctness and induction
The correctness of a divide-and-conquer algorithm is proved by an induction that follows the structure of the recursion. The induction is on the problem size. First one shows that the algorithm is correct in the base case. Then one assumes it is correct for all smaller inputs and shows that the combine step produces the right result. For findMax this goes as follows.
For every range with lo ≤ hi, findMax(a, lo, hi) returns the maximum element of a[lo..hi].
The induction is on the number of elements in the range, k = hi − lo + 1. If k = 1, then lo = hi and the method returns a[lo], which is the maximum of a one-element range. Now let k ≥ 2 and assume the method is correct on every range with fewer than k elements. For mid = ⌊(lo + hi)/2⌋ we have lo ≤ mid < hi. Both halves are therefore nonempty, and each contains fewer than k elements. By the induction hypothesis, left is the maximum of the left half and right is the maximum of the right half. Every element of the range lies in one of the two halves; hence the maximum of the range is max(left, right). ∎
The inequality lo ≤ mid < hi used in the proof is important. If the split leaves one of the halves empty, or leaves a half as large as the whole range, the induction hypothesis cannot be applied and the program can recurse forever. For example, if mid were rounded up, with the left half [lo..mid] and the right half [mid+1..hi], then on a two-element range mid = hi and the right half would be empty. The same question must be asked of every divide-and-conquer algorithm: is each subproblem really smaller, and how is an empty subproblem handled?
1.2Recurrence relations
The running time of a recursive algorithm is written in terms of itself: the time for a problem of size n is expressed through the times of smaller problems and the cost of splitting and combining. An equation of this kind is called a recurrence relation. This section briefly recalls what divide and conquer needs from the setting up and solving of recurrences with the master theorem.
1.2.1Setting up the recurrence
A recurrence is read off the code of the algorithm by asking three questions:
- How many recursive calls are made? This number is a. Only calls that actually run are counted. Binary search contains two separate call lines, but only one of them runs in each execution; hence a = 1.
- How large is the input of each call? If the input is n/b, read off b. If the input shrinks by a constant amount, such as n − 1, the recurrence does not fit the form of the master theorem.
- How much work is done outside the calls? The total cost of splitting and combining is f(n). Loops, array copying, and building sublists belong to this cost.
The recurrences of the following algorithms are written down by looking at their code.
findMax: two calls, each on a half range; one comparison outside: T(n) = 2T(n/2) + O(1).- Merge sort: two calls, each on a half array; outside, a linear loop that merges the two halves: T(n) = 2T(n/2) + O(n).
- Binary search: one call (left or right half), a constant number of comparisons: T(n) = T(n/2) + O(1).
- Fast exponentiation:
power(x, n)callspower(x, n/2)once and performs at most two multiplications: T(n) = T(n/2) + O(1). Here n is the value of the exponent, not the length of the input. - Naive recursive Fibonacci: two calls, but on inputs n − 1 and n − 2: T(n) = T(n − 1) + T(n − 2) + O(1). This recurrence is not in the form of the master theorem.
1.2.2The master theorem
The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n) without computation. It compares f(n), which stands for the work at the root, with nlogb a, which stands for the total work at the leaves. The second value is called the leaf work, and its exponent logb a is the critical exponent: the recursion tree has logb n levels, and the number of nodes multiplies by a at each level; the number of leaves is alogb n = nlogb a.
Let a ≥ 1 and b > 1 be constants, let f(n) be an asymptotically positive function, and let T(n) = aT(n/b) + f(n). With c = logb a:
- If f(n) = O(nc − ε) for some ε > 0, then T(n) = Θ(nc). (Case 1: the leaves dominate.)
- If f(n) = Θ(nc), then T(n) = Θ(nc log n). (Case 2: every level contributes equally.)
- If f(n) = Ω(nc + ε) for some ε > 0, and the regularity condition a · f(n/b) ≤ k · f(n) holds for some constant k < 1 and all sufficiently large n, then T(n) = Θ(f(n)). (Case 3: the root dominates.)
The language of the theorem looks heavy at first, but using it is short: compare f(n) with nlogb a; the larger one wins; if the two are of the same order, a factor of log n is added to the result. "Polynomially smaller" means that the gap is at least a power such as nε. A gap of only a log n factor does not count as a polynomial gap.
Three recurrences are solved with the master theorem.
- T(n) = 4T(n/2) + n: a = 4, b = 2, nlog2 4 = n2. f(n) = n is polynomially smaller than n2 (ε = 1). Case 1: T(n) = Θ(n2).
- T(n) = 2T(n/2) + n2: nlog2 2 = n. f(n) = n2 is polynomially larger. Regularity condition: 2 · (n/2)2 = n2/2 ≤ ½ · n2; it holds with k = ½. Case 3: T(n) = Θ(n2).
- T(n) = 2T(n/2) + 1 (
findMax): nlog2 2 = n, f(n) = 1 = n0. The gap is n1. Case 1: T(n) = Θ(n). This agrees with the count of n − 1 comparisons and 2n − 1 calls.
1.2.3Level sums in the recursion tree
The three cases of the master theorem become clear on their own once one looks at the total work on each level of the recursion tree. At level i there are ai subproblems, each of size n/bi. The total work done at this level is ai · f(n/bi). The total running time of the algorithm is the sum over all levels. From the root to the leaves, the level sums either grow, stay constant, or shrink. Table 1.2 gives the level sums of five recurrences for n = 16.
| Recurrence | 0 | 1 | 2 | 3 | 4 | Total | Trend |
|---|---|---|---|---|---|---|---|
| 2T(n/2) + n | 16 | 16 | 16 | 16 | 16 | 80 | constant (case 2) |
| 3T(n/2) + n | 16 | 24 | 36 | 54 | 81 | 211 | ×1.5 (case 1) |
| 4T(n/2) + n | 16 | 32 | 64 | 128 | 256 | 496 | ×2 (case 1) |
| 7T(n/2) + n2 | 256 | 448 | 784 | 1372 | 2401 | 5261 | ×1.75 (case 1) |
| 2T(n/2) + n2 | 256 | 128 | 64 | 32 | 16 | 496 | ×0.5 (case 3) |
The table shows the three behaviors side by side. In the first row every level does the same work: 16. Since there are log2 n + 1 levels, the total is of order n log n; this is case 2 and the recurrence of merge sort. In the second, third, and fourth rows the level sums grow geometrically. In a geometric series the total is a constant multiple of the last term, and the last term is the leaf level. For 3T(n/2) + n the leaf level is 34 = 81 = 16log2 3. This is the Karatsuba recurrence, and its running time is Θ(nlog2 3). In the last row the level sums halve. This time the total is a constant multiple of the first term, that is, of the root: Θ(n2).
This view also explains where the speedup in divide and conquer comes from. The only difference between 4T(n/2) + n and 3T(n/2) + n is that one subproblem is missing at each level. But this difference compounds at every level: at n = 16 the leaf level has 81 units of work instead of 256. As n grows, the ratio grows like (4/3)log2 n = n2 − 1.585.
1.2.4The algorithms of this chapter and the master theorem
Table 1.3 solves the recurrences of the algorithms discussed in these notes with the master theorem. What the calculations have in common is that a, b, and f(n) are read off the code and the critical exponent is compared with the exponent of f(n).
| Algorithm | a | b | f(n) | nlogb a | Case | T(n) |
|---|---|---|---|---|---|---|
| Binary search, fast exponentiation | 1 | 2 | 1 | n0 = 1 | 2 | Θ(log n) |
| Merge sort, closest pair, balanced quicksort | 2 | 2 | n | n | 2 | Θ(n log n) |
| Maximum element | 2 | 2 | 1 | n | 1 | Θ(n) |
| Karatsuba | 3 | 2 | n | n1.585 | 1 | Θ(n1.585) |
| Naive block matrix multiplication | 8 | 2 | n2 | n3 | 1 | Θ(n3) |
| Strassen | 7 | 2 | n2 | n2.807 | 1 | Θ(n2.807) |
The last three rows of the table carry a common lesson. The entire gain of Karatsuba and Strassen comes from reducing a by one: from 4 to 3 and from 8 to 7. The cost of splitting and combining, f(n), does not shrink; it even grows slightly. In case 1 the running time depends only on the critical exponent, which is logb a. When a gets smaller, the exponent gets smaller too: log2 4 = 2 but log2 3 ≈ 1.585; log2 8 = 3 but log2 7 ≈ 2.807.
1.2.5Recurrences the master theorem cannot handle
The master theorem is powerful but fits a narrow pattern: all subproblems must have the same size, and the size must shrink by a ratio. Some divide-and-conquer algorithms do not fit this pattern:
- Shrinking by a constant amount. The recurrence T(n) = T(n − 1) + n has no b. Unbalanced quicksort and worst-case Quickhull behave this way. Unrolling the recurrence gives n + (n − 1) + … + 1 = n(n + 1)/2 = Θ(n2).
- Unequal splits. The recurrence of Quickhull is T(n) = T(n1) + T(n2) + O(n), where n1 and n2 depend on the input. Splits in a fixed but unequal ratio, such as T(n) = T(n/3) + T(2n/3) + n, also fall outside the theorem. These are solved with a recursion tree: in the last example every level sums to at most n and the longest branch has log3/2 n levels; the result is Θ(n log n).
- f(n) that falls between the cases. In T(n) = 2T(n/2) + n/log n, f(n) = n/log n is smaller than n but not polynomially smaller: the gap is only a factor of log n. No case of the theorem applies. Similarly, the recurrence 2T(n/2) + n log n of the flawed version of the closest pair of points lies outside the three cases of the master theorem; its solution is Θ(n log2 n).
Forcing the master theorem onto a recurrence that does not fit the pattern. For T(n) = T(n − 1) + n, saying "a = 1, f(n) = n, case 3, result Θ(n)" is wrong; the correct result is Θ(n2). Before applying the theorem, check that the recurrence has the form aT(n/b) + f(n), that b > 1, and that f(n) falls into one of the three cases.
1.3Basic examples
Merge sort, quicksort, and binary search are familiar algorithms. This section does not explain them again; it merely sets them side by side as three different faces of the same paradigm. Two new examples follow: fast exponentiation, which brings exponentiation down to logarithmic time, and the recursive Fibonacci computation, where divide and conquer gives a bad result.
1.3.1Classic divide-and-conquer algorithms
Table 1.4 collects the divide and combine steps and the recurrences of the algorithms named in these notes in a single table. It is instructive to read the table column by column rather than row by row. In the "Combine" column two algorithms have "none": in binary search and quicksort the work is either done at splitting time or the result comes directly from a single subproblem.
| Algorithm | Divide | Combine | Recurrence | Time |
|---|---|---|---|---|
| Binary search | inspect the middle element, discard one half | none | T(n/2) + O(1) | O(log n) |
| Merge sort | split the array in the middle | merge the sorted halves | 2T(n/2) + O(n) | O(n log n) |
| Quicksort | partition around a pivot | none (in place) | T(k) + T(n − k − 1) + O(n) | avg. O(n log n) |
| Fast exponentiation | xn = (x⌊n/2⌋)2 · (x) | square the result | T(n/2) + O(1) | O(log n) |
| Quickhull | build a triangle with the farthest point | add the hull pieces | T(n1) + T(n2) + O(n) | avg. O(n log n) |
| Closest pair of points | split in the middle by x | scan the middle strip | 2T(n/2) + O(n) | O(n log n) |
| Karatsuba | split the number into two halves | add up 3 products | 3T(n/2) + O(n) | O(n1.585) |
| Strassen | split the matrix into 4 blocks | add up 7 products | 7T(n/2) + O(n2) | O(n2.807) |
1.3.2Merge sort: the work is in the merge
Merge sort is the plainest example of divide and conquer. The divide step splits the array in the middle and takes O(1), since it computes only a middle index. In the conquer step the two halves are sorted recursively. In the combine step the two sorted halves are merged in a single pass, at each step taking the smaller of the two front elements; this step takes Θ(n).
[38, 27, 43, 3, 9, 82, 10]. The top three rows show the splitting, the "Base" row the single-element arrays, and the bottom three rows the merges. The last row is the sorted array: [3, 9, 10, 27, 38, 43, 82].Figure 1.3 shows the sorting of a seven-element array level by level. First, with mid = (0 + 6)/2 = 3, the array is split into the halves [38 27 43 3] and [9 82 10]. The halves are split again: [38 27], [43 3], [9 82], [10]. One-element arrays are already sorted and are the base case. Merging works from the bottom up. First the pairs become [27 38], [3 43], [9 82]. Then [3 27 38 43] and [9 10 82] are obtained; finally these two give [3 9 10 27 38 43 82]. Each merge takes as many steps as the sum of the lengths of the two halves. All the merges on one level together touch at most n elements. The number of levels is ⌈log2 7⌉ = 3.
The recurrence is T(n) = 2T(n/2) + Θ(n) and falls under case 2 of the master theorem: Θ(n log n). Because the split is always made in the middle without looking at the input, this running time is the same in the best, average, and worst case. The most important observation from the paradigm's point of view is this: the real work is done in the merge. All the comparisons are in the merge loop; the split looks at no element.
1.3.3Quicksort: the work is in the partition
Quicksort solves the same problem from the opposite direction. The divide step picks a pivot element and separates the array into the elements smaller and larger than the pivot. This operation is called partitioning and takes Θ(n). In the conquer step the two parts are sorted recursively. There is no combine step: because the parts are sorted in place, the two sorted parts already sit side by side in the right order. Unlike merge sort, the real work is done in the partition.
[10, 80, 30, 90, 40, 50, 70]. Left: the state after the first partition; the pivot 70 has settled at index 4. Right: the sorted array.The example in Figure 1.4 uses Lomuto partitioning: the last element of the range is the pivot. Table 1.5 gives the order of the calls.
| Call | Pivot | New index | Left part | Right part | Array |
|---|---|---|---|---|---|
partition(arr, 0, 6) | 70 | 4 | [10 30 40 50] | [90 80] | 10 30 40 50 70 90 80 |
partition(arr, 0, 3) | 50 | 3 | [10 30 40] | [—] | 10 30 40 50 70 90 80 |
partition(arr, 0, 2) | 40 | 2 | [10 30] | [—] | 10 30 40 50 70 90 80 |
partition(arr, 0, 1) | 30 | 1 | [10] | [—] | 10 30 40 50 70 90 80 |
partition(arr, 5, 6) | 80 | 5 | [—] | [90] | 10 30 40 50 70 80 90 |
The first partition can be called balanced: parts of four and two elements result. But the left part [10 30 40 50] is already sorted. Because the last element is the pivot, each partition separates only one element. The pivots 50, 40, and 30 settle at the end one after another, and the right part stays empty each time. This is the worst split in divide and conquer: 1 + (n − 1).
The running time of quicksort depends on the balance of the split. If the pivot is near the median, the recurrence is T(n) = 2T(n/2) + O(n) and the time is O(n log n); this is the average case. On sorted input, if the last element is chosen as the pivot, each partition separates one element; the recurrence becomes T(n) = T(n − 1) + O(n) and the time O(n2). The remedy is to choose the pivot independently of the input: a random pivot, or the median of the first, middle, and last elements.
Comparing the two sorting algorithms shows the flexibility of the paradigm. The work must be done somewhere. Quicksort divides cleverly first, and the combine comes for free. Merge sort divides blindly and combines cleverly. Merge sort guarantees balance but needs an extra array; quicksort works in place but leaves the balance to the choice of pivot.
1.3.4Binary search: decrease and conquer
In a sorted array, binary search compares the middle element with the target value and discards one half of the array entirely. The search continues only in the remaining half. The recurrence is T(n) = T(n/2) + O(1); here a = 1, b = 2, nlog2 1 = n0 = 1 and f(n) = 1 are of the same order. Case 2 gives Θ(log n). In an array of a million elements, at most 20 probes suffice.
Binary search has a single subproblem and no combine step. For this reason some sources call it not divide and conquer but decrease and conquer: the problem is not split, only reduced. The distinction is terminological; the analysis uses the same recurrence. The real observation is this: if one of the subproblems can be discarded, the gain is large. Linear search takes O(n), binary search O(log n).
1.3.5Fast exponentiation
The naive way to compute xn is to multiply x by itself n − 1 times. For n = 106 that means 999,999 multiplications. With divide and conquer, far fewer multiplications suffice. The observation is simple:
xn = (xn/2)2 (n even), xn = x · (x⌊n/2⌋)2 (n odd).
For example, 313 = 3 · (36)2, 36 = (33)2, and 33 = 3 · (31)2. The problem xn reduces to a single subproblem whose exponent is half as large. The result of the subproblem is computed once and multiplied by itself. The base case is x0 = 1.
long power(long x, int n) {
if (n == 0) return 1; // base
long y = power(x, n / 2);
if (n % 2 == 0) return y * y; // even
return x * y * y; // odd
}The most important line of the code is long y = power(x, n / 2);. The value for the half exponent is stored in a variable and used twice: for even n the method returns y * y, for odd n it returns x * y * y. Each call therefore makes only one recursive call and adds at most two multiplications. The recurrence is T(n) = T(n/2) + O(1) and the result is O(log n). The number of calls is one more than the number of digits in the binary representation of n; the number of multiplications is at most 2(⌊log2 n⌋ + 1).
1.3.6Code trace: power(3, 13)
When power(3, 13) is called, the exponent halves at each call: 13 → 6 → 3 → 1 → 0. The calls first descend along this chain, and the multiplications are performed as the values come back. Table 1.6 gives the return order.
| Call | y | n even? | Returned value | Multiplications |
|---|---|---|---|---|
power(3, 0) | — | base | 1 | 0 |
power(3, 1) | 1 | odd | 3 · 1 · 1 = 3 | 2 |
power(3, 3) | 3 | odd | 3 · 3 · 3 = 27 | 2 |
power(3, 6) | 27 | even | 27 · 27 = 729 | 1 |
power(3, 13) | 729 | odd | 3 · 729 · 729 = 1,594,323 | 2 |
power(3, 13) and its return values. The chain does not branch: each call makes a single subcall. The equalities in the bottom row show the decomposition 313 = 3 · (36)2.The total number of multiplications is 2 + 2 + 1 + 2 = 7; the naive method would make 12. The difference is small for small exponents and striking for large ones. At n = 106, fast exponentiation makes 21 calls and 27 multiplications; the naive method makes 999,999 multiplications.
A warning: the long type holds at most 263 − 1 ≈ 9.22 · 1018. The value 339 ≈ 4.05 · 1018 fits, but 340 ≈ 1.22 · 1019 does not, and Java overflows without raising an error. In real applications, fast exponentiation is used either with BigInteger or by taking the remainder modulo some number after every multiplication (xn mod m). The second form is the basis for computing very large exponents in public-key cryptography.
Not using the variable y and recomputing the half exponent at every use, for example writing return power(x, n / 2) * power(x, n / 2); for even n and return x * power(x, n / 2) * power(x, n / 2); for odd n. The code still gives the right result, but each call now makes two recursive calls. The recurrence becomes T(n) = 2T(n/2) + O(1), and case 1 of the master theorem gives Θ(n): the logarithmic gain is lost completely. This version makes 31 calls for power(3, 11) and 63 for power(2, 16); the correct version makes 5 and 6. Solving the same subproblem twice is an expensive habit in divide and conquer.
1.3.7An unsuitable case: overlapping subproblems
The Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2). The definition is recursive and can be turned directly into code:
long fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}The code has the divide-and-conquer form: the problem is split into two smaller subproblems, the subproblems are solved by the same function, and the results are combined by addition. The result is also correct. But this is a bad example, because the subproblems are not independent of each other. To compute F(n − 1), F(n − 2) is already computed; then F(n − 2) is computed again from scratch in the second call.
fib(5). The highlighted nodes are repetitions of the same subproblem: F(3) is computed twice and F(2) three times.In the tree of Figure 1.6, fib(5) makes 15 calls. F(3) is computed twice, F(2) three times, F(1) five times, and F(0) three times. The number of calls grows by the formula C(n) = 2F(n + 1) − 1: fib(30) makes 2,692,537 calls and fib(40) makes 331,160,281. The recurrence is T(n) = T(n − 1) + T(n − 2) + O(1) and its solution is O(φn), where φ = (1 + √5)/2 ≈ 1.618 is the golden ratio.
The remedy is to store the result of each subproblem when it is first computed, and to read it from a table when it is needed a second time. This approach is called dynamic programming; for Fibonacci it brings the time down to O(n). The question to ask when choosing a paradigm is this: are the subproblems independent of each other, or do they contain shared sub-subproblems? If they are independent, divide and conquer is suitable; if they overlap, dynamic programming is. If the locally best choice at each step leads to the global optimum, the greedy approach gives an even simpler solution.
Assuming that a problem can be solved directly by divide and conquer because it has a recursive definition. A recursive definition gives a correct algorithm; it may not give a fast one. If the call tree shows several calls with the same argument, the subproblems overlap and the results should be stored.
1.4Convex hull and Quickhull
Computational geometry studies algorithms that work on points, lines, and polygons. One of the most basic problems of this field is the convex hull. Quickhull, the divide-and-conquer solution of the problem, takes its name from its resemblance to quicksort: a "pivot" is chosen, the points are partitioned around it, and the parts are processed recursively.
1.4.1The convex hull problem
A polygon is convex if the line segment joining any two points inside it lies entirely inside the polygon. The convex hull of a set S of n points in the plane is the smallest convex polygon that contains all the points of S.
There is an easy way to keep the definition in mind. Imagine nails driven into a board at the positions of the points, with a rubber band stretched around all of them. When released, the band wraps around the outer nails and tightens. The shape the band takes is the convex hull. The analogy also shows two important facts. First, the vertices of the hull are points of S; the band touches only nails. Second, the inner nails have no effect on the shape of the band.
The output of the algorithm is the ordered list of the vertices of the hull; by convention they are listed counterclockwise. It is not enough to answer only "which points are on the hull?", because the order of the vertices is needed to draw the polygon or compute on it. The hull of the set in Figure 1.7 has seven vertices; the remaining nine points are inside.
The convex hull is the first step of many applications. In games and robotics, collision detection speeds up by using the hull of a complex object in its place: if two hulls do not intersect, the objects do not intersect either. Geographic information systems draw the boundary of the observation points in a region with a hull. In image processing the hull of a shape summarizes its form. The two points of a set that are farthest from each other are always vertices of the hull; this observation shrinks the farthest-pair problem. In clustering, the boundary of each cluster is shown by its hull.
1.4.2The Quickhull algorithm
Quickhull rests on this observation: the point farthest from a line is always part of the hull of the points on that side of the line. The algorithm works in the following steps:
- The point A with the smallest x coordinate and the point B with the largest are found. Both are on the hull: the leftmost and rightmost points can never lie between other points.
- The line AB separates the points into two subsets: above the line (to the left when looking from A to B) and below it (to the right).
- In one subset the point C farthest from AB is found. C is on the hull.
- The points inside the triangle ACB are eliminated: since the vertices of the triangle are on the hull, the interior of the triangle lies inside the hull, and these points cannot be vertices of the hull.
- The same procedure is applied recursively to the points outside AC and the points outside CB.
- When no points remain outside an edge, that edge is a hull edge and the recursion stops. The points found make up the hull.
The resemblance to quicksort is clear. In quicksort the pivot splits the array into two parts; in Quickhull the farthest point C splits the set into two parts according to the two sides of the triangle. There is one difference: in Quickhull's partitioning some points fall into neither part. The points inside the triangle are discarded entirely, and this discarding is the main reason the algorithm is fast in practice.
The algorithm has almost no combine step. Each recursive call adds the point it finds to the hull list; the results of the two subcalls are not combined separately. The work is done at splitting time, as in quicksort: finding the farthest point and separating the points by the sides of the triangle.
1.4.3The orientation test and distance
The algorithm keeps asking two geometric questions: is a point P to the left or to the right of the line A → B? And how far is P from AB? Both questions are answered by a single formula. The formula uses only integer multiplication and subtraction; no angles, square roots, or division are needed.
long cross(Point A, Point B, Point P) {
return (long)(B.x - A.x) * (P.y - A.y)
- (long)(B.y - A.y) * (P.x - A.x);
}The method cross computes the z component of the cross product of the vectors A → B and A → P. The (long) casts prevent the int product from overflowing for large coordinates. The sign of the value gives the direction:
cross > 0: P is to the left of A → B (a counterclockwise turn).cross < 0: P is to the right of A → B (a clockwise turn).cross = 0: A, B, and P lie on the same line.
The absolute size of the value carries meaning too. |cross| is twice the area of the triangle with vertices A, B, and P. The area of the triangle is also ½ · |AB| · h, where h is the perpendicular distance of P from the line AB. This gives |cross| = |AB| · h. For the same A and B, |AB| is constant. The point farthest from the line is therefore the point with the largest cross value, and there is no need to compute the distance separately.
cross is positive; Q is to the right and cross is negative. The dashed line is the perpendicular distance of P from the line.Let A = (2, 18) and B = (35, 11). Then B − A = (33, −7).
- For C = (13, 27), C − A = (11, 9): cross = 33 · 9 − (−7) · 11 = 297 + 77 = 374.
- For (28, 23), (26, 5): cross = 33 · 5 − (−7) · 26 = 165 + 182 = 347.
- For (10, 5), (8, −13): cross = 33 · (−13) − (−7) · 8 = −429 + 56 = −373; the point is below the line.
The first two points are above the line. Since 374 is larger than 347, C = (13, 27) is farther from the line. The actual distance is 374 / |AB| = 374 / √(332 + 72) = 374 / √1138 ≈ 11.09, but this division is unnecessary for the comparison.
Mixing up the point order in the orientation test. cross(A, B, P) and cross(B, A, P) have opposite signs. Quickhull finds the upper subset with leftOf(P, A, B) and the lower subset with leftOf(P, B, A): the same test, applied to the other side by reversing the direction of the line. If the order is mixed up, one subset is processed twice and the other not at all.
1.4.4Code: quickHull() and find()
void quickHull(List<Point> P) {
Point A = leftmost(P), B = rightmost(P);
hull.add(A); hull.add(B);
find(leftOf(P, A, B), A, B); // upper set
find(leftOf(P, B, A), B, A); // lower set
}
void find(List<Point> S, Point A, Point B) {
if (S.isEmpty()) return; // AB is a hull edge
Point C = farthest(S, A, B); // max cross
hull.add(C);
find(leftOf(S, A, C), A, C); // outside AC
find(leftOf(S, C, B), C, B); // outside CB
} // inside ACB is droppedThe code consists of two methods. quickHull is the starter: it finds the leftmost and rightmost points, adds them to the hull, and calls find for the two halves. find(S, A, B) works on the set S lying to the left of the line A → B and finds the hull vertices in this set:
if (S.isEmpty()) return;is the base case. If no points lie outside the line, AB is a hull edge.Point C = farthest(S, A, B);selects the point with the largestcrossvalue, andhull.add(C);adds it to the hull.- The two recursive calls work on the points to the left of A → C and to the left of C → B. Points that fall into neither of these two sets are inside the triangle and are eliminated automatically; there is no separate code for them.
Processing the lower subset in the direction B → A involves a subtlety. The part below the line is to the right of A → B, that is, to the left of B → A. This lets find always work under the convention "points to the left of the line", so a single method serves both sides. The helper methods used in the code follow. leftmost and rightmost scan the list once and return the points with the smallest and largest x.
List<Point> leftOf(List<Point> S, Point A, Point B) {
List<Point> result = new ArrayList<>();
for (Point p : S)
if (cross(A, B, p) > 0) result.add(p); // left of A→B
return result;
}
Point farthest(List<Point> S, Point A, Point B) {
Point best = null;
long bestVal = -1;
for (Point p : S) {
long c = cross(A, B, p);
if (c > bestVal) { bestVal = c; best = p; }
}
return best;
}leftOf and farthest each scan the list once; both take O(|S|). A find call therefore does work proportional to the size of its own set: one farthest scan and two leftOf scans.
The list hull keeps the vertices in the order they are found, and this is not the order around the perimeter of the polygon. For ordered output it suffices to move the line hull.add(C) between the two recursive calls. In that case, the vertices of the upper subset are added from A to B and those of the lower subset from B to A; if A is written first and B between the two subsets, the vertices come out in clockwise order. Reversing the list gives counterclockwise order.
1.4.5Code trace: 16 points
The trace uses the 16 points of Figure 1.7: (2,18), (4,25), (10,5), (11,16), (13,27), (14,19), (16,12), (20,16), (20,2), (21,12), (23,20), (24,15), (27,9), (27,15), (28,23), (35,11). The leftmost point is A = (2, 18) and the rightmost is B = (35, 11); both are added to the hull. Of the remaining 14 points, 8 are to the left of A → B (the upper subset) and 6 are to the right (the lower subset). Table 1.7 gives the find calls in order.
| Call | Line | |S| | Farthest C | Dropped | Outside AC | Outside CB |
|---|---|---|---|---|---|---|
| 1 | (2,18) → (35,11) | 8 | (13,27) | 4 | 1 | 2 |
| 2 | (2,18) → (13,27) | 1 | (4,25) | 0 | 0 | 0 |
| 3 | (2,18) → (4,25) | 0 | S empty: hull edge | |||
| 4 | (4,25) → (13,27) | 0 | S empty: hull edge | |||
| 5 | (13,27) → (35,11) | 2 | (28,23) | 1 | 0 | 0 |
| 6 | (13,27) → (28,23) | 0 | S empty: hull edge | |||
| 7 | (28,23) → (35,11) | 0 | S empty: hull edge | |||
| 8 | (35,11) → (2,18) | 6 | (20,2) | 4 | 0 | 1 |
| 9 | (35,11) → (20,2) | 0 | S empty: hull edge | |||
| 10 | (20,2) → (2,18) | 1 | (10,5) | 0 | 0 | 0 |
| 11 | (20,2) → (10,5) | 0 | S empty: hull edge | |||
| 12 | (10,5) → (2,18) | 0 | S empty: hull edge | |||
The first row of the table is the algorithm's most efficient moment. Of the 8 points of the upper subset, the farthest is C = (13, 27); its cross value is 374. The four points inside the triangle, (14,19), (20,16), (24,15), and (27,15), are eliminated in a single move. Only (4,25) remains outside AC, and (23,20) and (28,23) remain outside CB. The numbers add up: 8 = 1 + 4 + 1 + 2 (C, the dropped points, and the two outer sets).
Call 2 processes a one-point set. A single point is naturally the farthest: (4,25) joins the hull and the two subcalls return with empty sets. Call 5 has two points: for the line (13,27) → (35,11), (28,23) is farther (cross = 152); (23,20) lies inside the triangle and is eliminated. In the lower subset, call 8 selects C = (20, 2) (cross = 402) and eliminates the points (11,16), (16,12), (21,12), and (27,9). The one remaining point, (10,5), joins the hull in call 10.
At the end of the trace the hull has seven vertices: (2,18), (35,11), (13,27), (4,25), (28,23), (20,2), (10,5). Nine points have been eliminated, and 12 find calls have been made. The number of calls is determined by the structure: each vertex added to the hull inside find opens two subcalls, and each hull edge ends in an empty call. Here 5 vertices were found inside find (5 non-empty calls), and the 7 edges of the hull gave 7 empty calls.
1.4.6An example with 104 points
The power of the algorithm shows more clearly on large sets. In a set of 104 points, the leftmost point is (−14, 46) and the rightmost is (106, 20). The line joining these two points has 71 points above it and 31 below. Table 1.8 gives only the non-empty calls, that is, the calls that add a point to the hull. The "Candidates" column is the number of points that have been neither added to the hull nor eliminated; at the start it is 71 + 31 = 102.
| Line | |S| | Farthest | Dropped | Candidates left |
|---|---|---|---|---|
| (−14,46) → (106,20) | 71 | (54,120) | 56 | 45 |
| (−14,46) → (54,120) | 6 | (8,84) | 2 | 42 |
| (−14,46) → (8,84) | 1 | (−4,69) | 0 | 41 |
| (8,84) → (54,120) | 2 | (42,111) | 1 | 39 |
| (54,120) → (106,20) | 8 | (104,74) | 6 | 32 |
| (54,120) → (104,74) | 1 | (77,103) | 0 | 31 |
| (106,20) → (−14,46) | 31 | (11,−25) | 25 | 5 |
| (106,20) → (11,−25) | 5 | (88,−5) | 4 | 0 |
The first call alone eliminates 56 points, and the first call in the lower subset eliminates 25. Of the 94 eliminated points, 81 come from these two calls. The sets of the later calls are small: 6, 1, 2, 8, 1, 5 points. With 8 non-empty calls in all, the 10 vertices of the hull are found and 94 points are eliminated. Because most of the points are eliminated at every step, the work shrinks quickly. This is typical for uniformly distributed random points: the number of hull vertices is very small relative to n, and the vast majority of points fall inside the first few triangles.
1.4.7Analysis and other hull algorithms
Each find call scans its own set a constant number of times: once to find the farthest point and twice to separate the two outer sets. The work of a call is O(|S|). The recurrence has the form
T(n) = T(n1) + T(n2) + O(n), n1 + n2 ≤ n − 1
Since n1 and n2 depend on the input, the master theorem does not apply, and the cases are examined separately:
- Average case. If the splits are balanced and many points are eliminated at each step, the time is O(n log n). On uniformly distributed random points in the plane, the algorithm is often even faster than this, because the eliminated points never descend into the deep levels of the recursion.
- Worst case. At each step the farthest point may separate only a single point. For example, the points may lie along a convex curve, with the farthest point always falling next to an end. In this case the recurrence becomes T(n) = T(n − 1) + O(n) and the time is O(n2). On this input no point is eliminated; all the points are on the hull.
- Output-sensitive bound. Let h be the number of hull vertices. The sets on one level of the recursion tree are disjoint; the total work of a level is therefore at most n. Because the non-empty calls along every root-to-leaf path find different vertices, the depth of the tree does not exceed h. The total work is O(n · h). When the number of vertices is small, this bound is even better than n log n.
There are other algorithms for the convex hull. Table 1.9 compares them by running time.
| Algorithm | Time | Approach |
|---|---|---|
| Brute force (every candidate edge) | O(n3) | a pair of points is a hull edge if all the other points lie on the same side of it |
| Jarvis march (gift wrapping) | O(n · h) | start from one vertex and at each step wrap to the next outermost vertex |
| Graham scan | O(n log n) | sort the points by angle and discard right turns with a stack |
| Andrew's monotone chain | O(n log n) | sort the points by x and build the upper and lower chains separately |
| Quickhull | avg. O(n log n), worst O(n2) | divide and conquer; farthest point and elimination inside the triangle |
| Chan | O(n log h) | hulls of small groups by Graham, merged by Jarvis |
It is not possible to go below these times. An algorithm that finds a convex hull can also solve the sorting problem: the numbers x1, …, xn to be sorted are placed on the parabola y = x2 as the points (xi, xi2). Since the parabola is convex, all the points are vertices of the hull, and the ordered vertex list of the hull gives the numbers in sorted order. Since sorting in the comparison model requires Ω(n log n) time, the convex hull requires at least that much time as well. In this sense the Graham and Andrew algorithms are optimal. The O(n log h) time of Chan's algorithm does not contradict this lower bound, because in the parabola example h = n.
1.5The closest pair of points
Finding the two closest points among points in the plane is one of the oldest problems of computational geometry. The brute-force solution looks at all pairs and takes quadratic time. The divide-and-conquer solution brings the time down to O(n log n). The interesting part of the solution is the combine step: a geometric observation is needed so as not to miss pairs that straddle the boundary between the two halves.
1.5.1The problem and brute force
Let a set of n ≥ 2 points in the plane be given. The closest pair of points problem asks for the pair p ≠ q with the smallest Euclidean distance
d(p, q) = √((px − qx)2 + (py − qy)2)
(or only for this smallest distance).
The problem arises in many applications. In air traffic control, the two aircraft that come closest to each other are monitored continuously. Clustering algorithms proceed by merging the two closest points or clusters. In collision detection, the two closest objects are the first candidate pair. In geographic data, facilities that lie close to each other are found.
The most direct solution is to compute the distance of all pairs and take the smallest:
double bruteForce(List<Point> p) {
double min = Double.MAX_VALUE;
for (int i = 0; i < p.size(); i++)
for (int j = i + 1; j < p.size(); j++)
min = Math.min(min, dist(p.get(i), p.get(j)));
return min;
}The two nested loops try each pair once: j is always greater than i, so neither both (p, q) and (q, p) are tried, nor is a point compared with itself. The number of pairs is n(n − 1)/2 and the time is O(n2). For 10 points, 45 distances are computed; for n = 106, about 5 · 1011 distances are needed. On a modern computer this is a job that takes minutes.
In one dimension the problem is easy. The numbers are sorted and only consecutive numbers are compared: the two closest numbers are always adjacent in the sorted array. The time is that of sorting: O(n log n). In two dimensions this idea does not work directly. When the points are sorted by x, two points with close x values can be far apart because their y values differ greatly. Two points that are not adjacent in the array sorted by x can also be the closest pair. Divide and conquer overcomes this difficulty.
1.5.2Divide and conquer: the middle strip
The algorithm works in the following steps:
- The points are sorted once by x and once by y. These two sorted lists are called X and Y. Sorting is done only at the start, before the recursion.
- Divide: The vertical line L through the x coordinate of the point in the middle of X splits the points into a left half and a right half.
- Conquer: The closest distance in each half is found recursively: δL and δR. The smaller of the two is δ = min(δL, δR).
- Combine: A closer pair may still exist: a pair with one point on the left and the other on the right. If such a pair exists, it crosses L and both of its points are closer than δ to L. Only the points with |x − L| < δ are therefore examined, that is, the points of the strip of width 2δ.
- The strip is scanned in y order. Each point is compared only with the points that come after it and whose y difference is less than δ.
The reasoning behind the combine step is as follows. Pairs with both points in the same half have already been examined in the recursion, and none is closer than δ. Only the pairs that cross L remain. If the distance of such a pair is less than δ, then its x difference is also less than δ; both points are therefore at most δ away from L. Likewise, the y difference must be less than δ. Scanning the strip in y order is the cheap way to check this second condition: as soon as the y difference exceeds δ, the following points are even farther away and the inner loop stops.
1.5.3Why at most seven neighbors in the strip?
The strip can be crowded. On a bad input all the points may fall in the strip. Trying every pair of strip points would again take quadratic time. The observation that makes the algorithm fast is that it suffices to compare each point in the strip with only a constant number of its neighbors.
Let the strip points be sorted by y. The number of strip points that come after a point p and whose y difference from it is less than δ is at most 7.
The points that come after p and whose y difference is less than δ lie inside a rectangle of width 2δ and height δ whose bottom edge is at the y level of p. The rectangle is split in two by L, and each half is a δ × δ square. Each square is divided into four small squares of side δ/2, giving 8 small squares in all. A small square lies entirely within one half. If a small square contained two points, both would be in the same half, and the distance between them would be at most the diagonal of the square, that is, δ/√2 < δ. Yet the closest distance in that half is at least δ; a contradiction. Hence each small square contains at most one point. One of these points is p itself; at most 7 points remain. ∎
The theorem gives the bound; the code does not write this bound explicitly. The inner loop stops when the y difference exceeds δ. The theorem guarantees that under this condition the inner loop runs at most 7 iterations. Some sources lower the bound to 6 or even 5; the value of the constant does not change the order of the running time. What matters is that the strip scan takes O(7n) = O(n).
Believing that the total number of points in the strip is bounded. The strip can contain all n points; what is bounded is the number of neighbors each point is compared with. Another mistake is to scan the strip points in x order. The neighbor bound holds only in y order; in a strip scanned in x order, one point may have to be compared with many points.
1.5.4Code: closest()
double closest(List<Point> X, List<Point> Y) {
int n = X.size(), mid = n / 2;
if (n <= 3) return bruteForce(X);
Point m = X.get(mid); // Yl/Yr: halves of Y
double dl = closest(X.subList(0, mid), Yl);
double dr = closest(X.subList(mid, n), Yr);
double d = Math.min(dl, dr);
List<Point> strip = new ArrayList<>(); // strip
for (Point p : Y) // y order
if (Math.abs(p.x - m.x) < d) strip.add(p);
for (int i = 0; i < strip.size(); i++) {
Point p = strip.get(i);
for (int j = i + 1; j < strip.size()
&& strip.get(j).y - p.y < d; j++)
d = Math.min(d, dist(p, strip.get(j)));
}
return d;
}The method takes two lists: X is the list of points sorted by x, and Y is the list of the same points sorted by y. Before the first call, all the points are sorted once by the two separate criteria. The lines work as follows:
if (n <= 3) return bruteForce(X);is the base case. For three or fewer points, brute force computes at most three distances; splitting is not worth it. There is one more reason for the cutoff of 3: in a half with a single point, the closest pair is undefined.Point m = X.get(mid);determines the dividing line: L is the line x = m.x. The left half isX.subList(0, mid)and the right half isX.subList(mid, n).YlandYrare the points ofYthat fall into the two halves, and they preserve the y order. The code skips over how they are built with a comment line; one way is given below.- The two recursive calls give
dlanddr;dis the smaller of them. - The first
forloop builds the strip. Because it walks overY, the strip is automatically sorted by y; no further sorting is needed. - The nested loops scan the strip. The condition of the inner loop is
strip.get(j).y - p.y < d; asdshrinks, the loop stops earlier. If a closer pair is found,dis updated.
List<Point> Yl = new ArrayList<>(), Yr = new ArrayList<>();
Set<Point> leftHalf = new HashSet<>(X.subList(0, mid));
for (Point p : Y) // y order is kept
if (leftHalf.contains(p)) Yl.add(p);
else Yr.add(p);This fragment builds Yl and Yr in a single pass. The points of the left half are put into a HashSet; Y is walked in order, and each point is appended to one of the two lists depending on whether it is in the left half. Because the Point class does not override equals, the set works by object identity; even two different points with the same coordinates do not get mixed up. The pass takes expected O(n) time, and the lists preserve the y order. No re-sorting is done.
1.5.5Code trace: 10 points
The trace uses ten points: (2,3), (12,30), (40,50), (5,1), (12,10), (3,4), (7,7), (17,17), (27,27), (28,27). The list sorted by x is X = [(2,3), (3,4), (5,1), (7,7), (12,30), (12,10), (17,17), (27,27), (28,27), (40,50)]. The points (12,30) and (12,10), which have the same x, keep their input order because the sort is stable. The list sorted by y is Y = [(5,1), (2,3), (3,4), (7,7), (12,10), (17,17), (27,27), (28,27), (12,30), (40,50)].
| Step | Call | Event | Result |
|---|---|---|---|
| 1 | X[0..9] | n = 10 > 3; mid = 5, m = (12, 10); 5 points left, 5 right | — |
| 2 | X[0..4] | n = 5; mid = 2, m = (5, 1); 2 points left, 3 right | — |
| 3 | X[0..1] | brute force: (2,3), (3,4) | 1.41 |
| 4 | X[2..4] | brute force: (5,1), (7,7), (12,30); closest (5,1)–(7,7) | 6.32 |
| 5 | X[0..4] | d = min(1.41; 6.32) = 1.41 | — |
| 6 | X[0..4] | strip |x − 5| < 1.41: [(5,1)]; no comparison | 1.41 |
| 7 | X[5..9] | n = 5; mid = 2, m = (27, 27); 2 points left, 3 right | — |
| 8 | X[5..6] | brute force: (12,10), (17,17) | 8.60 |
| 9 | X[7..9] | brute force: (27,27), (28,27), (40,50); closest (27,27)–(28,27) | 1.00 |
| 10 | X[5..9] | d = min(8.60; 1.00) = 1.00 | — |
| 11 | X[5..9] | strip |x − 27| < 1: [(27,27)]; no comparison | 1.00 |
| 12 | X[0..9] | d = min(1.41; 1.00) = 1.00 | — |
| 13 | X[0..9] | strip |x − 12| < 1: [(12,10), (12,30)]; y difference 20 ≥ 1, no comparison | 1.00 |
The result is d = 1.00; the closest pair is (27,27)–(28,27). This pair was found by brute force at the base, in the right half of the right half. In this example the strips make no pair comparisons at all. The reason is that δ turns out small early, and the strips become very narrow. The algorithm's total work is 8 distance computations (1 at step 3, 3 at step 4, 1 at step 8, 3 at step 9). Brute force on the same input would compute 45 distances.
An example where the strip actually does work should also be seen. Let L be at x = 10, and let the two halves return δL = 5 and δR = 4. Let the list Y be (8,1), (13,2), (11,4), (7,6), (12,9), (9,10), (15,12).
- d = min(5, 4) = 4. The strip is built with the condition |x − 10| < 4: (15,12) is left out; the strip holds, in y order, (8,1), (13,2), (11,4), (7,6), (12,9), (9,10).
- (8,1): the distance to (13,2) is √26 ≈ 5.10, so d does not change. To (11,4) it is √18 ≈ 4.24, no change. The y difference of (7,6) is 5 ≥ 4; the inner loop stops.
- (13,2): to (11,4) it is √8 ≈ 2.83; d = 2.83. The y difference of (7,6) is 4 ≥ 2.83; it stops.
- (11,4): to (7,6) it is √20 ≈ 4.47, no change. The y difference of (12,9) is 5; it stops.
- (7,6): the y difference of (12,9) is 3 ≥ 2.83; no comparison is made.
- (12,9): to (9,10) it is √10 ≈ 3.16, no change. End of the strip.
In all, 5 distances are computed. The result is d ≈ 2.83 and the pair is (13,2)–(11,4). This pair crosses L: one point is on the right and the other on the left. Searching the two halves separately would not have found it; the combine step caught it.
1.5.6Analysis
| Step | Cost | Note |
|---|---|---|
| Presorting by x and by y | O(n log n) | only once, before the recursion |
Splitting (X in two, Y into Yl/Yr preserving order) | O(n) | no re-sorting |
| Building the strip | O(n) | Y is already sorted by y |
| Scanning the strip | O(7n) = O(n) | at most 7 neighbors per point |
| Total | O(n log n) | T(n) = 2T(n/2) + O(n) |
At every level of the recursion, splitting, building the strip, and scanning the strip together take O(n). The recurrence is the same as that of merge sort: T(n) = 2T(n/2) + O(n), with result O(n log n). Since the two initial sorts also take O(n log n), the total time is O(n log n). This time is optimal. In the algebraic decision tree model, even testing whether all the points are distinct requires Ω(n log n). Whether the closest distance is zero answers this very question.
Re-sorting the strip in every call. If, instead of using the list Y, the strip points are taken in x order and sorted by y at every call, the combine cost becomes O(n log n). The recurrence turns into T(n) = 2T(n/2) + O(n log n) and the result is O(n log2 n). The difference looks small, but for n = 220, with log2 n = 20, it means 20 times as much extra work. The right way is to compute the y order once and preserve it while splitting.
The choice of the base case also affects the algorithm. If the cutoff were n ≤ 1 instead of n ≤ 3, a half with a single point would return Double.MAX_VALUE, effectively infinity. The result would still be correct. A two-point range is split into two single points and d stays infinite. The strip contains both points, and the strip scan finds the pair that would escape. But the number of calls grows, and on small inputs unnecessary recursion overhead arises.
1.6Karatsuba multiplication
Multiplying two integers looks like something the computer does in a single instruction. This is true only as long as the numbers fit in a machine word, for example 64 bits. In cryptography, scientific computing, and computer algebra, numbers with hundreds or thousands of digits are multiplied. These numbers are stored as digit arrays, and the time of multiplication depends on the number of digits. In 1960 Kolmogorov conjectured that multiplying two n-digit numbers requires Ω(n2) operations. Anatoly Karatsuba, then still a student, soon found an algorithm showing this conjecture to be false.
1.6.1The schoolbook method and naive splitting
In the multiplication method learned in primary school, each digit of the second number is multiplied by each digit of the first, and the shifted partial results are added up. For two n-digit numbers, n2 single-digit multiplications are performed: the time is O(n2).
The first attempt at divide and conquer is to split the numbers in two. The n-digit numbers x and y are split at the point m = ⌊n/2⌋:
x = a · 10m + b, y = c · 10m + d
Here a and c are the upper halves of the numbers, and b and d the lower halves. For example, 1234 = 12 · 100 + 34. Expanding the product gives
x · y = ac · 102m + (ad + bc) · 10m + bd
Multiplying by 10m merely appends m zeros on the right and takes O(n); the additions also take O(n). The real work is the four half-size products: ac, ad, bc, bd. The recurrence is T(n) = 4T(n/2) + O(n). In the master theorem nlog2 4 = n2 dominates and the result is O(n2). Naive splitting yields no gain: each of the four products takes n2/4, and the total is again n2.
1.6.2Three products instead of four
Karatsuba's observation is that the middle term ad + bc does not need two separate products. The following identity holds:
(a + b)(c + d) = ac + (ad + bc) + bd ⇒ ad + bc = (a + b)(c + d) − ac − bd
ac and bd will be computed anyway. Once one more product, (a + b)(c + d), is made, the middle term is obtained with two subtractions. The three products are named as follows:
z2 = ac, z0 = bd, z1 = (a + b)(c + d), x · y = z2 · 102m + (z1 − z2 − z0) · 10m + z0
The price of getting rid of one product is a few extra additions and subtractions. The additions take O(n); the products are each a half-size problem and are solved recursively. The recurrence becomes T(n) = 3T(n/2) + O(n).
Compute 1234 · 5678. Here n = 4, m = 2, and 10m = 100.
- Split: a = 12, b = 34, c = 56, d = 78.
- z2 = 12 · 56 = 672, z0 = 34 · 78 = 2652.
- z1 = (12 + 34)(56 + 78) = 46 · 134 = 6164.
- Middle term: z1 − z2 − z0 = 6164 − 672 − 2652 = 2840. Check: ad + bc = 12 · 78 + 34 · 56 = 936 + 1904 = 2840.
- Result: 672 · 104 + 2840 · 102 + 2652 = 6,720,000 + 284,000 + 2652 = 7,006,652.
1.6.3Code: karatsuba()
long karatsuba(long x, long y) {
if (x < 10 || y < 10) return x * y; // base
int n = Math.max(digits(x), digits(y));
long p = (long) Math.pow(10, n / 2);
long a = x / p, b = x % p; // x = a·p + b
long c = y / p, d = y % p; // y = c·p + d
long z0 = karatsuba(b, d);
long z1 = karatsuba(a + b, c + d);
long z2 = karatsuba(a, c);
return z2 * p * p + (z1 - z2 - z0) * p + z0;
}The code is a direct counterpart of the formula:
if (x < 10 || y < 10) return x * y;is the base case. If one of the factors has a single digit, the product is computed directly. It matters that the condition uses "or": in a product like 7 · 15, splitting is meaningless, because 7 has no upper half.nis the larger of the digit counts of the two numbers;p = 10n/2is the split point.Math.powreturns adouble; since small powers of 10 are represented exactly indouble, the(long)cast is safe.a = x / pandb = x % pare the upper and lower halves;canddare the same fory.- The three recursive calls compute
z0,z1, andz2in turn. The last line combines the results.
The helper method that gives the digit count is simple:
int digits(long x) {
return String.valueOf(Math.abs(x)).length();
}This Java code is meant to show the algorithm. Since the long type holds numbers of at most 19 digits, it cannot be used for large numbers. Real implementations store numbers as digit arrays; in Java this is done with the BigInteger class. The correctness of the code can still be checked: on 100,000 randomly chosen pairs of numbers, karatsuba(x, y) and x * y gave the same result.
1.6.4Code trace: 1234 · 5678
In the call karatsuba(1234, 5678), n = 4 and p = 100. The call makes three subcalls for (34, 78), (46, 134), and (12, 56). Table 1.12 gives all the calls in the order they are made.
| Call | n, p | a, b, c, d | Combine | Return |
|---|---|---|---|---|
| (1234, 5678) | 4, 100 | 12, 34, 56, 78 | 672 · 104 + (6164 − 672 − 2652) · 100 + 2652 | 7,006,652 |
| (34, 78) | 2, 10 | 3, 4, 7, 8 | 21 · 100 + (105 − 21 − 32) · 10 + 32 | 2652 |
| 4 · 8, 7 · 15, 3 · 7 | base | direct product | 32, 105, 21 | |
| (46, 134) | 3, 10 | 4, 6, 13, 4 | 52 · 100 + (170 − 52 − 24) · 10 + 24 | 6164 |
| 6 · 4 | base | direct product | 24 | |
| (10, 17) | 2, 10 | 1, 0, 1, 7 | 1 · 100 + (8 − 1 − 0) · 10 + 0 | 170 |
| 0 · 7, 1 · 8, 1 · 1 | base | direct product | 0, 8, 1 | |
| 4 · 13 | base | direct product | 52 | |
| (12, 56) | 2, 10 | 1, 2, 5, 6 | 5 · 100 + (33 − 5 − 12) · 10 + 12 | 672 |
| 2 · 6, 3 · 11, 1 · 5 | base | direct product | 12, 33, 5 | |
karatsuba(1234, 5678). Each node is a product; the number below it is the value it returns. Green nodes are base cases.The interesting point of the trace is the call (46, 134). When the sums of the halves are taken for z1, the numbers can grow by one digit: 12 + 34 = 46 has two digits, but 56 + 78 = 134 has three. The code handles this automatically: n is the larger of the digit counts of the two numbers, and p = 10⌊3/2⌋ = 10 is chosen. The split becomes 46 = 4 · 10 + 6 and 134 = 13 · 10 + 4. This one-digit growth does not change the order of the running time.
In all, 16 calls are made: 1 root, 3 children, 9 grandchildren, and the 3 children of (10, 17). Of these, 11 calls are base cases. The schoolbook method makes 16 single-digit multiplications for the same product. In this small example the gain is not evident, because some of the base-case products (7 · 15, 4 · 13, 3 · 11) are larger than single-digit products. The gain shows up on large numbers.
1.6.5Analysis and practice
The recurrence is T(n) = 3T(n/2) + O(n). Here nlog2 3 ≈ n1.585 is polynomially larger than f(n) = n. Case 1 of the master theorem gives T(n) = Θ(nlog2 3) ≈ Θ(n1.585). The same result is found by counting. For numbers of n = 2k digits, the number of products triples at every level, and after k levels one reaches the single-digit products. The number of single-digit products is 3k = 3log2 n = nlog2 3. For example, for n = 8, 33 = 27 products are made; the schoolbook method makes 64.
| n (digits) | n2 | n1.585 | Ratio |
|---|---|---|---|
| 10 | 100 | 38 | 2.6× |
| 100 | 10,000 | 1,479 | 6.8× |
| 1,000 | 1.0 · 106 | 56,871 | 17.6× |
| 10,000 | 1.0 · 108 | 2.2 · 106 | 45.7× |
| 1.0 · 106 | 1.0 · 1012 | 3.2 · 109 | 309.2× |
The ratio grows like n0.415: about 18 times at a thousand digits and about 300 times at a million digits. However, the table does not show constant factors. At every level Karatsuba uses extra additions, subtractions, and temporary numbers. On small numbers this overhead outweighs the gain, and Karatsuba is slower than the schoolbook method. Implementations therefore use a cutoff: when the number drops below a certain digit count, they switch to the schoolbook method.
Java's BigInteger.multiply method follows this approach: it uses the schoolbook method on small numbers, Karatsuba on large ones, and the Toom-Cook method on larger ones still. Toom-Cook is a generalization of Karatsuba's idea: it splits the number into three parts and makes five products instead of nine, giving a time of O(nlog3 5) ≈ O(n1.465). Even faster algorithms are based on the fast Fourier transform. The Schönhage–Strassen algorithm takes O(n log n log log n). The algorithm announced by Harvey and van der Hoeven in 2019 takes O(n log n). This last algorithm is of theoretical importance; because its constants are very large, it is not used in practice.
1.7Strassen matrix multiplication
Karatsuba's idea also applies to matrices. In 1969 Volker Strassen showed that two matrices can be multiplied faster than by the classical Θ(n3) method. The method again rests on removing one recursive call: seven block products instead of eight.
1.7.1Classical and block matrix multiplication
Each cell of the product C = A · B of two n × n matrices A and B is the inner product of a row of A with a column of B: C[i][j] = Σk A[i][k] · B[k][j]. The classical method writes this definition as three nested loops:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
C[i][j] += A[i][k] * B[k][j];For each of the n2 cells, n products are made: n3 products in all. The code assumes C starts out filled with zeros; in Java a newly created array is already filled with zeros.
The first attempt at divide and conquer is to split each matrix into four blocks of size n/2 × n/2:
A = [A11 A12; A21 A22], B = [B11 B12; B21 B22], C = [C11 C12; C21 C22]
Blocks can be multiplied and added like numbers; only the order of the factors in a product cannot be changed. The blocks of the result are:
- C11 = A11 · B11 + A12 · B21
- C12 = A11 · B12 + A12 · B22
- C21 = A21 · B11 + A22 · B21
- C22 = A21 · B12 + A22 · B22
Eight block products and four block additions are needed. A block addition adds (n/2)2 cells and takes Θ(n2). The recurrence is T(n) = 8T(n/2) + Θ(n2); nlog2 8 = n3 dominates and the result is Θ(n3). As with naive splitting in Karatsuba, splitting alone is not enough; the number of products must be reduced.
1.7.2Seven products instead of eight
Strassen showed that all four result blocks can be obtained from suitable sums of seven intermediate products. Table 1.14 gives these products and the result blocks.
| Product | Definition | Result block |
|---|---|---|
| P1 | A11 · (B12 − B22) | C11 = P5 + P4 − P2 + P6 |
| P2 | (A11 + A12) · B22 | C12 = P1 + P2 |
| P3 | (A21 + A22) · B11 | C21 = P3 + P4 |
| P4 | A22 · (B21 − B11) | C22 = P5 + P1 − P3 − P7 |
| P5 | (A11 + A22) · (B11 + B22) | |
| P6 | (A12 − A22) · (B21 + B22) | |
| P7 | (A11 − A21) · (B11 + B12) |
The correctness of the formulas is checked by expanding them. C12 is the easiest: P1 + P2 = A11B12 − A11B22 + A11B22 + A12B22 = A11B12 + A12B22. For C11, expanding P5, P4, P2, and P6 gives twelve terms. Ten of them cancel in pairs, leaving A11B11 + A12B21. The order of the factors must be preserved here: for matrices, A11B11 and B11A11 are generally different. Strassen's formulas never use the commutativity of multiplication; they are therefore valid for blocks as well.
Besides the seven products, 18 block additions or subtractions are made: 10 in the definitions of the P's and 8 in the result blocks. The blocks are in turn multiplied recursively by Strassen; the base case is a 1 × 1 matrix, that is, the product of two single numbers.
1.7.3Step by step: a 2 × 2 example
Let A = [[1, 3], [7, 5]] and B = [[6, 8], [4, 2]]. Since the blocks are 1 × 1, each block is a single number: A11 = 1, A12 = 3, A21 = 7, A22 = 5; B11 = 6, B12 = 8, B21 = 4, B22 = 2.
- P1 = 1 · (8 − 2) = 6
- P2 = (1 + 3) · 2 = 8
- P3 = (7 + 5) · 6 = 72
- P4 = 5 · (4 − 6) = −10
- P5 = (1 + 5) · (6 + 2) = 48
- P6 = (3 − 5) · (4 + 2) = −12
- P7 = (1 − 7) · (6 + 8) = −84
- C11 = 48 + (−10) − 8 + (−12) = 18, C12 = 6 + 8 = 14, C21 = 72 + (−10) = 62, C22 = 48 + 6 − 72 − (−84) = 66.
The result is C = [[18, 14], [62, 66]]. Check by the classical method: 1 · 6 + 3 · 4 = 18, 1 · 8 + 3 · 2 = 14, 7 · 6 + 5 · 4 = 62, 7 · 8 + 5 · 2 = 66. Strassen used 7 products; the classical method uses 8.
Making a sign error in Strassen's formulas. C22 = P5 + P1 − P3 − P7; P7 is subtracted. If "+ P7" is written, the program produces a wrong matrix without raising any error: in the example above, C22 comes out as 48 + 6 − 72 + (−84) = −102 instead of 66. This kind of error cannot be caught by the compiler or the runtime. Comparing the implementation with the classical method on small random matrices exposes the bug at once.
1.7.4Analysis and practice
The recurrence is T(n) = 7T(n/2) + Θ(n2). Here nlog2 7 ≈ n2.807 is polynomially larger than n2, and case 1 of the master theorem gives T(n) = Θ(nlog2 7) ≈ Θ(n2.807). Counting shows the same thing: for n = 2k the number of scalar products is 7k; the classical method makes 8k = n3 products. On 16 × 16 matrices, Strassen makes 2401 products and the classical method 4096. For n = 1024 = 210, 710 ≈ 2.8 · 108 and 810 ≈ 1.07 · 109; Strassen makes about 3.8 times fewer products.
The algorithm has some problems in practice:
- Size. If n is not a power of 2, the matrix is padded with zeros up to the nearest power. The zeros do not change the result, but they add work.
- Cutoff. Because of the 18 extra additions and the temporary matrices, Strassen is slower than the classical method at small n. Libraries switch to the classical method once the submatrix size drops to about 64–128.
- Numerical stability. With floating-point numbers, the subtractions can amplify rounding error. The classical method is more reliable in this respect.
- Memory. Temporary blocks are created at every level; the extra memory is O(n2).
After Strassen, smaller upper bounds were found for the exponent ω of matrix multiplication. As of 2024 the best known bound is ω < 2.372. The constants of these algorithms are so large that they are not used in practice. Strassen's real lesson is theoretical: trading a multiplication for additions lowers the exponent by reducing a by one. The same idea appears in Karatsuba's drop from 4 to 3 and in Strassen's from 8 to 7.
1.8Assessment
Table 1.15 sets the naive method and the divide-and-conquer solution side by side for the problems discussed in these notes.
| Problem | Naive method | Divide and conquer | Recurrence |
|---|---|---|---|
| Sorting | O(n2) (bubble sort) | O(n log n) | 2T(n/2) + n |
| Searching a sorted array | O(n) | O(log n) | T(n/2) + 1 |
| Exponentiation xn | O(n) products | O(log n) | T(n/2) + 1 |
| Convex hull | O(n3) | avg. O(n log n) | T(n1) + T(n2) + n |
| Closest pair of points | O(n2) | O(n log n) | 2T(n/2) + n |
| Integer multiplication | O(n2) | O(n1.585) | 3T(n/2) + n |
| Matrix multiplication | O(n3) | O(n2.807) | 7T(n/2) + n2 |
The gain comes from three sources. First, the work is split in a balanced way and combined in O(n) at each level: sorting and the closest pair of points. Second, the number of subproblems is reduced: Karatsuba and Strassen. Third, one of the subproblems is discarded entirely, or the result of a single subproblem is reused: binary search and fast exponentiation. Quickhull is a mix of the first and third kinds: the points inside the triangle are discarded, and the remaining work is split into two unbalanced parts.
When deciding whether to solve a problem by divide and conquer, ask the following questions. Can the problem be split into smaller pieces of the same kind? Are the pieces independent of each other? Can the solutions of the pieces be combined more cheaply than by the naive method? If the answers to the first two are yes and the third is no, divide and conquer gives a correct but slow algorithm, as in the maximum-element example. If the pieces overlap, dynamic programming is more suitable; if the locally best choice at each step suffices, the greedy approach is.
1.9Common mistakes
- Forgetting the base case or writing a base case that is never reached. The result is infinite recursion and a
StackOverflowError. In Karatsuba the base case isx < 10 || y < 10. If this line is deleted, then on single-digit numbers p = 100 = 1.karatsuba(4, 8)callskaratsuba(0, 0)in its first subcall; that call in turn calls itself with the same arguments, and the recursion never ends. - Unbalanced splits. Choosing the last element as the pivot on a sorted array, or separating only one point at each step in Quickhull, gives T(n) = T(n − 1) + n = O(n2).
- Not noticing overlapping subproblems. Computing Fibonacci by plain recursion takes exponential time; dynamic programming, which stores the results, is needed.
- Calling the same subproblem twice. Calling
power(x, n / 2)twice in fast exponentiation raises Θ(log n) to Θ(n). - Underestimating the combine cost. Sorting the strip at every call in the closest pair of points makes the time O(n log2 n); 2T(n/2) + n log n ≠ Θ(n log n).
- Using the master theorem in the wrong place. T(n) = T(n − 1) + n, unequal splits, and functions that fall between the cases, such as f(n) = n/log n, are outside the scope of the theorem.
- Sign and direction errors. A single sign error in C22 = P5 + P1 − P3 − P7 of Strassen produces a wrong matrix without any error message. In Quickhull, if the point order passed to
crossis mixed up, the upper and lower subsets swap places. Comparing with the naive method on a small example catches these errors. - Believing that divide and conquer always speeds things up. In the maximum-element problem divide and conquer also makes n − 1 comparisons; the gain is parallelism, not running time.
1.10Summary
- Divide and conquer splits the problem into smaller, independent subproblems of the same kind, solves the subproblems recursively, and combines the results. A base case is essential.
- The running time is expressed by the recurrence T(n) = aT(n/b) + f(n). The master theorem compares f(n) with nlogb a: if the leaves dominate, the result is Θ(nlogb a); if they are equal, a factor of log n is added; if the root dominates, Θ(f(n)).
- For unequal splits or splits that shrink by a constant amount, the master theorem does not apply; the recursion tree is used.
- In merge sort the real work is in the merge; in quicksort it is in the partition. Binary search and fast exponentiation take O(log n) with a single subproblem.
- If subproblems overlap (Fibonacci), divide and conquer takes exponential time; dynamic programming is needed.
- Quickhull starts from the leftmost and rightmost points, at each step adds the point farthest from the line (the largest
cross) to the hull, and eliminates the inside of the triangle. It takes O(n log n) on average, O(n2) in the worst case, and O(n · h) output-sensitively. - In the closest pair of points, the points are split in two by x, δ = min(δL, δR) is taken, and the strip of width 2δ is scanned in y order. Each point is compared with at most 7 neighbors; the time is O(n log n).
- Karatsuba uses the identity ad + bc = (a + b)(c + d) − ac − bd to make three products instead of four: Θ(n1.585).
- Strassen makes seven block products instead of eight: Θ(n2.807). In both algorithms the gain comes from reducing a by one; on small inputs, below a cutoff, they switch to the naive method.
1.11Key terms
- divide and conquer
- base case
- subproblem
- recursion
- recurrence (relation)
- recursion tree
- master theorem
- merge sort
- quicksort
- partition
- binary search
- overlapping subproblems
- dynamic programming
- convex hull
- closest pair of points
- brute force
- lower bound
- Karatsuba multiplication
- Strassen's algorithm
1.12Test Yourself
What are the solutions of the following recurrences by the master theorem? (a) T(n) = 3T(n/3) + n, (b) T(n) = T(n/2) + n, (c) T(n) = 16T(n/4) + n2.
Answer
(a) nlog3 3 = n = f(n); case 2: Θ(n log n). (b) nlog2 1 = 1, and f(n) = n is polynomially larger; regularity f(n/2) = n/2 ≤ ½ · n holds; case 3: Θ(n). (c) nlog4 16 = n2 = f(n); case 2: Θ(n2 log n).
The method
findMaxis called asfindMax(a, 0, 5)on the array[3, 8, 1, 9, 4, 6]. How many calls and how many comparisons are made in total, and what is the result?Answer
For six elements the recursion tree has 6 leaves and 5 internal nodes: 11 calls and 5 comparisons. The first split is
[0..2]and[3..5]; the maximum of the left half is 8 and that of the right half is 9. The result is 9.How many recursive calls and how many multiplications does
power(2, 25)make? How many multiplications does the naive method make?Answer
The sequence of exponents is 25 → 12 → 6 → 3 → 1 → 0: 6 calls. Multiplications: n = 1 (odd) 2, n = 3 (odd) 2, n = 6 (even) 1, n = 12 (even) 1, n = 25 (odd) 2; total 8. The result is 225 = 33,554,432. The naive method makes 24 multiplications.
Let A = (0, 0), B = (10, 0), and let the upper subset contain the points (2,3), (5,6), (8,2), (5,2). Which point does Quickhull choose as C? Which points are eliminated, and with which does the recursion continue?
Answer
cross(A, B, P) = 10 · Py: the values are 30, 60, 20, 20; C = (5, 6). cross(A, C, (2,3)) = 5 · 3 − 6 · 2 = 3 > 0: (2,3) is outside AC. For (8,2), cross(C, B, ·) = 5 · (−4) − (−6) · 3 = −2; for (5,2), cross(A, C, ·) = −20 and cross(C, B, ·) = −20: both are inside the triangle and are eliminated. The recursion continues on the AC side with (2,3) alone; the CB side is empty.
In the closest-pair algorithm the line L is at x = 10 and δ = 3 has been returned from the two halves. The list
Yis (9,1), (11,2), (14,4), (10,5), (8,6), (12,7). Which points make up the strip, how many distances are computed, and what is the result?Answer
For (14,4), |14 − 10| = 4 ≥ 3; it is outside the strip. The strip: (9,1), (11,2), (10,5), (8,6), (12,7). The distance (9,1)–(11,2) is √5 ≈ 2.24 and d becomes 2.24; the y difference of (10,5) is 4, so the inner loop stops. After (11,2), the y difference of (10,5) is 3; it stops. (10,5)–(8,6) = 2.24 and (10,5)–(12,7) ≈ 2.83 are computed. (8,6)–(12,7) ≈ 4.12 is computed. In all, 4 distances; the result is d = √5 ≈ 2.24.
Which subcalls are made in the call
karatsuba(56, 78)? How many calls are made, and how many of them are base cases?Answer
p = 10; a = 5, b = 6, c = 7, d = 8. z0 = 6 · 8 = 48 (base). z1 = karatsuba(11, 15): the inner split gives 1, 1, 1, 5; the inner products are 1 · 5 = 5, 2 · 6 = 12, 1 · 1 = 1; the result is 100 + (12 − 1 − 5) · 10 + 5 = 165. z2 = 5 · 7 = 35 (base). The result is 35 · 100 + (165 − 35 − 48) · 10 + 48 = 4368. In all, 7 calls, 5 of them base cases.
What are P1, …, P7 and C when the matrices A = [[1, 0], [2, 1]] and B = [[3, 1], [0, 2]] are multiplied with Strassen's method?
Answer
P1 = 1 · (1 − 2) = −1, P2 = (1 + 0) · 2 = 2, P3 = (2 + 1) · 3 = 9, P4 = 1 · (0 − 3) = −3, P5 = (1 + 1)(3 + 2) = 10, P6 = (0 − 1)(0 + 2) = −2, P7 = (1 − 2)(3 + 1) = −4. C11 = 10 − 3 − 2 − 2 = 3, C12 = −1 + 2 = 1, C21 = 9 − 3 = 6, C22 = 10 − 1 − 9 + 4 = 4. C = [[3, 1], [6, 4]]; the classical method gives the same result.
Karatsuba's idea is generalized: numbers are split into three parts, and five products are made instead of nine partial products. If splitting and combining take O(n), what is the running time of the algorithm? Is it faster than Karatsuba?
Answer
T(n) = 5T(n/3) + O(n). nlog3 5 ≈ n1.465 dominates; case 1: Θ(n1.465). It is asymptotically faster than Karatsuba's n1.585; because its constants are larger, it pulls ahead only on larger numbers. This is the Toom-Cook method.
How many calls does the naive recursive
fib(6)make? Why is divide and conquer unsuitable here?Answer
C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1: C(5) = 15, C(4) = 9, C(6) = 25. The subproblems are not independent: while F(4) is computed, F(3), F(2), … are already computed, and they are recomputed from the other branch. If the results are stored (dynamic programming), each F(k) is computed once and the time is O(n).
1.13Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 4: gives Strassen's algorithm, the recursion-tree and substitution methods, and the proof of the master theorem. Chapter 33 treats the convex hull and the closest pair of points.
- J. Kleinberg, É. Tardos, Algorithm Design (2005), Chapter 5: explains divide-and-conquer recurrences intuitively; contains readable treatments of the closest pair of points and integer multiplication.
- C. B. Barber, D. P. Dobkin, H. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls" (1996): the paper that generalizes Quickhull to higher dimensions and forms the basis of the widely used Qhull software.
- V. Strassen, "Gaussian Elimination is not Optimal" (1969): the original paper, only a few pages long, that introduced the seven-product idea.
1.14References
- C. B. Barber, D. P. Dobkin, H. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls", ACM Transactions on Mathematical Software 22(4), 1996.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 4: Divide-and-Conquer; Chapter 33: Computational Geometry).
- A. Karatsuba, Yu. Ofman, "Multiplication of Multidigit Numbers on Automata", 1962.
- J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005 (Chapter 5: Divide and Conquer).
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
- V. Strassen, "Gaussian Elimination is not Optimal", Numerische Mathematik 13, 1969.
Related pages: Chapter 1 slides · © Sercan Külcü. All rights reserved.