Algorithms II (CS31005) Partha Bhowmick

Autumn 2012 CSE, IIT Kharagpur

Divide and Conquer

Believe it can be done. When you be-

lieve something can be done, really be-
lieve, your mind will find the ways to
do it. Believing a solution paves the
way to solution.
— David Joseph Schwartz

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the
same type, until they become simple enough to be solved directly. The solutions to the sub-problems are
then combined to give a solution to the original problem.

Example 0.1 Binary search, Quicksort, Merge sort, Multiplication of two complex numbers, Integer
multiplication, Matrix multiplication (Strassen’s algorithm), Closest pair in a point set, Convex hull, etc.

1 Integer Multiplication1
Consider the computation involved in finding (a + bi)(c + di). If we express it as (ac − bd) + (bc + ad)i,
then we need 4 scalar multiplications. But, as bc + ad = (a + b)(c + d) − ac − bd, so it can be done with
just three: ac, bd, (a + b)(c + d). Historically, it was first noticed by the mathematician, Carl Friedrich
Gauss (1777–1855).
We can extend the above idea to multiply two binary numbers a and b. Let, for simplicity, a and b have
n bits each, and n is a power of 2. Then we can express a as a concatenation of two binary numbers, aL
followed by aR , each of length n/2 bits, so that a “looks like” aL aR and its value is a = 2n/2 aL + aR .
Similarly, b = 2n/2 bL +bR . Thus, ab = (2n/2 aL +aR )(2n/2 bL +bR ) = 2n aL bL +2n/2 (aL bR +aR bL )+aR bR +,
which can be computed from the four n/2-bit numbers (aL etc.) by three multiplications between n/2-bit
numbers: two for aL bL and aR bR , and one for (aL + aR )(bL + bR ), since aL bR + aR bL = (aL + aR )(bL +
bR ) − aL bL − aR bR .

1.1 Time complexity

Addition of two numbers takes linear time. Multiplication by a power of 2 also takes linear time. Hence,
n
T (n) = 3T ( ) + O(n) = O(nlog3 2 ) ≈ O(n1.59 ).
4
1 S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, McGraw-Hill, 2006.

1
2 Closest Pair
Given a set of points P = {p1 , . . . , pn }, the problem
is to find the minimum distance δmin between two
points of P . The naive algorithm

is to consider all n2 point-pairs of P , compute their distances, and find
n
the minimum of these 2 = O(n ) distances, which needs O(n2 ) time. An efficient algorithm based on
2

divide-and-conquer approach1 is given below, which needs O(n log n) time.

PL PR PL PR
QL QR Qy

6 13 17 8
2 11
7
δL 8 δR 6
3 15 16 5
4 10 δ L′′4 R4′′ δ
y = y4
7 δ 4 3 δ
1 12 L′4 R4′
5 2
9 14 1

δ δ = min(δL, δR ) δ δ = min(δL, δR )

lµ : x = xµ lµ : x = xµ
(a) (b)

Figure 1: Demonstration on a small point set P having 17 points. (a) Strips QL ⊆ PL and QR ⊆ PR .
(b) Points and their indices in Qy = QL ∪ QR , sorted on y-coordinates. Points from QL are stored as
gray points and those from QR as black points, in Qy .

2.1 Divide-and-Conquer Algorithm

1. Sort the points of P to Px and to Py using x- and y-coordinates, respectively.

(This step is out of recursion.)
2. Partition P into PL and PR by the vertical median-line lµ : x = xµ , using Px .
3. Recursively compute the minimum distances δL and δR for PL and PR , respectively.
4. δ 0 ← δ ← min(δL , δR ).
5. Traverse Py and append a point (x, y) ∈ Py to Qy (initialized as empty) if x ∈ [xµ − δ, xµ + δ].
If x ∈ [xµ − δ, xµ ], then mark it as gray; otherwise black (Fig. 2b).
Result: Qy (= QL ∪ QR ) is y-sorted.
6. Traverse Qy in order from first to last, and for each gray point pL ∈ Qy ,
(a) compute the distances of four black points following pL and four black points preceding pL
in Qy ;
(b) find the minimum δ 00 of the above eight distances;
(c) δ 0 ← min(δ 0 , δ 00 ).
7. return min(δ, δ 0 ).
1 M.I. Shamos and D. Hoey. Closest-point problems. Proc. FOCS, pp. 151–162, 1975.

2
 b b
C(PR ) C(PR )

a a
C(PL ) C(PL )

Finding the lower tangent Finding the upper tangent

upper tangent

C(PR )

C(PL )
C(P )

lower tangent
The lower and the upper tangents After merging C (PL ) and C (PR )

Figure 2: Divide-and-conquer approach to find the convex hull C (P ) of P : Recursively finding C (P ) using
the convex hulls C (PL ) and C (PR ) corresponding to PL and PR , and their lower and upper tangents.

Time complexity

Step 1: O(n log n), Step 2: O(1), Step 3: 2 × T (n/2), Step 4: O(1), Step 5: O(n).

Step 6(a): The four black points following pL in Qy would lie in the δ × δ square box, namely R00 ,
or/and above. (In Fig. 2b, there is one black point in R400 corresponding to Point 4.)
Also, there can be at most three other gray points in the δ × δ square box L00 containing pL . (In Fig. 2b,
there is no other gray point in L004 .)
In effect, there can be at most seven other (three gray and four black) points in R00 ∪ L00 . Hence, we
have to see at most seven points following pL to compute the distances of four black points following
pL in Qy .
Similar arguments apply also for computing the distances of four black points preceding pL in Qy .
So, Step 6(a) (and hence Steps 6(b) and 6(c)) needs O(1) time for each gray point pL ∈ Qy , thereby
requiring O(n) time for all gray points of Qy .

Hence, for Steps 2–7, the time complexity is T 0 (n) = 2T 0 (n/2) + O(n) = O(n log n), which, when added
with the time complexity of sorting (Step 1), gives the overall time complexity as:
T (n) = T 0 (n) + O(n log n) = O(n log n) .

3 Convex Hull by Divide-and-Conquer

1. If |P | ≤ 3, then compute C (P ) in O(1) time and return.
2. Partition P into PL and PR using the median of x-coordinates of points in P .
3. Recursively compute C (PL ) and C (PR ) for PL and PR respectively.

3
 4. Merge C (PL ) and C (PR ) to get C (P ) by computing their lower and upper tangents and deleting
all the vertices of C (PL ) and C (PR ) (except the vertex points of tangency) lying between these two
tangents1 (Fig. 2).
Finding the Lower Tangent:
Let a be the rightmost vertex of C (PL ) and b be the leftmost vertex of C (PR ).
(a) while ab is not a lower tangent for C (PL ) and C (PR )
i. while ab is not a lower tangent2 to C (PL )
a ← a + 1 (move a clockwise)
ii. while ab is not a lower tangent to C (PR )
b ← b − 1 (move b counterclockwise)
(b) return ab
The upper tangent can be obtained in a similar manner.

Time complexity: While finding a tangent, each vertex on each hull will be checked at most once (e.g.,
→
−
a + 1 will be checked only once—whether it lies to the left of the directed ray ba). Hence, the runtime to
find the two tangents is O(|C (PL ) | + |C (PR ) |) = O(n).
Hence, Step 4 (merging) of the algorithm needs O(n) time. Step 1 needs O(1) time and Step 2 needs
O(n) time for median-based partitioning. Step 3 is recursive. Thus, T (n) = 2T (n/2) + O(n), which solves
to O(n log n).

1 A lower (upper) tangent is the straight line that touches the two hulls such that all the vertices of the two hulls lie

above (below) the tangent.

2 ab is not a lower tangent if the vertex a + 1 of C (P ), lying next to a, lies to the left of the ray/vector directed from b
L
to a.