Divide and conquer

Why it exists

Many problems have the same shape at every scale: sorting a million numbers is two problems of sorting half a million plus some work to put the halves together. Divide and conquer turns that observation into an algorithm and into a recurrence. It is the source of the fastest known algorithms for sorting, searching ordered data, multiplying large numbers and matrices, finding the median, and many geometric problems. It also gives the questions of the syllabus a standard form: write the recurrence, then solve it.

Prerequisites

You need recursion and the call stack (recursion and the call stack) and the methods for solving recurrences (solving recurrences).

Precise definitions

Divide and conquer solves a problem of size $n$ in three steps:

1. Divide the input into $a$ smaller subproblems of the same kind, each of size about $n/b$ (the subproblems are independent: they do not share work).
2. Conquer each subproblem recursively. A subproblem smaller than a fixed constant (the base case) is solved directly.
3. Combine the answers of the subproblems into the answer of the whole problem.

The recurrence. If dividing and combining together cost $f(n)$, the running time satisfies $T(n) = a\,T(n/b) + f(n), \qquad T(n) = \Theta(1) \text{ for small } n.$ With $a = 1$ the method is sometimes called decrease and conquer (binary search, fast exponentiation): only one subproblem is solved.

Correctness is proved by strong induction on $n$: the base case is correct; if the recursive calls are correct for all sizes less than $n$, and the combine step turns correct answers of the parts into a correct answer of the whole, then the call for $n$ is correct.

Depth and space. If the problem is cut into pieces of size $n/b$ the recursion depth is $\lceil \log_b n \rceil$, so the stack uses $O(\log n)$ frames (plus whatever the algorithm stores in each frame, for example a temporary array in merge sort).

How it works

The skeleton.

solve(problem P of size n):
    if n is small: return the answer directly            /* base case */
    split P into a parts of size about n / b             /* divide: cost counted in f(n) */
    for each part: answer[i] = solve(part)               /* conquer: a recursive calls */
    return combine(answer[0..a-1])                       /* combine: cost counted in f(n) */

An example: maximum and minimum. To find the largest and the smallest of $n$ keys, a plain scan that updates both uses $2(n-1)$ comparisons. Divide and conquer: split the array into two halves, find the maximum and minimum of each, then compare the two maxima and the two minima (two comparisons). Two keys need only one comparison. The recurrence for the number of comparisons is $T(1) = 0,\quad T(2) = 1,\quad T(n) = 2\,T(n/2) + 2,$ and for $n$ a power of two the solution is $T(n) = 3n/2 - 2$ (check: $T(2) = 1$, $T(4) = 4$, $T(8) = 10$). The code below is what the animation runs; only the divide and conquer function is shown and the array is $31, 7, 45, 12, 50, 3, 28, 19$.

The table gives the measured comparison counts for $n = 2, 4, \ldots, 64$ next to the plain scan.

Two remarks. First, for $n$ that is not a power of two the same code can use a comparison more than $3n/2 - 2$: for $n = 6$ it uses $8$, not $7$, so the formula is for powers of two. Second, the saving does not come from recursion as such: comparing the keys in pairs first and then taking the larger of each pair for the maximum and the smaller for the minimum gives the same $3n/2 - 2$ with a loop. Divide and conquer is a way to find such an idea, not always the only way to write it.

Where the work is done. The recursion tree of $T(n) = a\,T(n/b) + f(n)$ has $a^i$ subproblems of size $n/b^i$ on level $i$, so level $i$ costs $a^i f(n/b^i)$, and there are $\log_b n$ levels. The Master theorem (solving recurrences) compares $f(n)$ with $n^{\log_b a}$ (the number of leaves):

• $f$ grows polynomially slower than $n^{\log_b a}$: the levels cost more and more going down, the leaves dominate, $T(n) = \Theta(n^{\log_b a})$. Example: maximum and minimum, $a = 2$, $b = 2$, $f = 2$: $\Theta(n)$. Strassen, Karatsuba.
• $f$ grows like $n^{\log_b a}$: every level costs about the same, $T(n) = \Theta(f(n) \log n)$ (for $f = \Theta(n^{\log_b a})$). Examples: merge sort, binary search ($a = 1$, $f = 1$: $\Theta(\log n)$).
• $f$ grows polynomially faster (with the regularity condition): the root dominates, $T(n) = \Theta(f(n))$. Example: $T(n) = 2T(n/2) + n^2$.

For the balanced case the table of a recursion tree makes it visible: every level costs $n$.

How the choices change the answer. Reducing the number of subproblems matters more than the cost of combining: $T(n) = 4T(n/2) + n$ is $\Theta(n^2)$ but $T(n) = 3T(n/2) + n$ is $\Theta(n^{1.585})$ (Karatsuba's idea), and $7T(n/2) + n^2$ is $\Theta(n^{2.807})$ against $8T(n/2) + n^2 = \Theta(n^3)$ (Strassen's idea). Both are on the next page.

Unbalanced division. Splitting into very unequal parts makes the tree deep: $T(n) = T(n-1) + n$ is $\Theta(n^2)$ (the worst case of quicksort), $T(n) = T(n/3) + T(2n/3) + n$ is still $\Theta(n \log n)$ because the depth stays logarithmic.

When divide and conquer is the wrong tool. The subproblems must be independent. The recursion for Fibonacci numbers, $F(n) = F(n-1) + F(n-2)$, makes two calls that both compute $F(n-2)$ and so on: the running time $T(n) = T(n-1) + T(n-2) + 1$ is exponential, $\Theta(\varphi^n)$ with $\varphi = 1.618$. When subproblems overlap, remember their answers: that is dynamic programming.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The simplest instance with one subproblem is binary search. The classic two-subproblem algorithms are merge sort and quicksort, and the standard collection of applications (Strassen, Karatsuba, closest pair, maximum subarray, selection) is on the next page, divide and conquer applications. Recurrences are solved by the methods of solving recurrences; repeating subproblems lead to dynamic programming.

PYQs

Exponentiation is a heavily used operation in
public key cryptography. Which of the following
options is the tightest upper bound on the number
of multiplications required to compute bnmod
m,0≤b , n≤m?

There are n unsorted arrays: A 1 , A 2 , ..., A n .
Assume that n is odd. Each of A 1 , A 2 , ..., A n
contains n distinct elements. There are no common
elements between any two arrays. The worst-case
time complexity of computing the median of the
medians of A 1 , A 2 , ..., A n is

Consider the following table:

Algorithms
Design
Paradigms
P
Kruskal
i
Divide and
Conquer
Q
Quicksort
ii
Greedy
R
Floyd-
Warshall
iii Dynamic
Programming

Given below are some algorithms, and some
algorithm design paradigms.
List - I
P. Dijkstra's Shortest Path
Q. Floyd-Warshall algorithm to compute all
pairs shortest path
R. Binary search on a sorted array
S. Backtracking search on a graph
List – II
i. Divide and Conquer
ii. Dynamic Programming
iii. Greedy design
iv. Depth-first search
v. Breadth-first search
Match the above algorithms on the left to the
corresponding design paradigm they follow.

Match the following:

(P) Prim's algorithm for
minimum spanning tree
(i) Backtracking
(Q) Floyd-Warshall
algorithm for all pairs
shortest paths
(ii) Greedy
method
(R) Mergesort
(iii) Dynamic
programming
(S) Hamiltonian circuit
(iv) Divide and
conquer

Self-check

Revision card

References