Divide and Conquer

Tutorial

Algorithm Analysis and Design

Plan

1. Solving recurrences 2.5

2. Fast Fourier transform 2.7, 2.8
3. Matrix squaring vs. multiplication 2.27
4. Closest pair of points 2.32
5. Polynomial interpolation 2.10

1/21
Solving recurrences - the recursion tree

n 1×n = n

n
n/2 n/2 2× 2
= n

n
n/4 n/4 n/4 n/4 4× 4
= n

.. ..
. .
1 1 ··· 1 1 n×1 = n

T (n) = 2T (n/2) + n: label each node with its own work, then sum level by level.

log n × |{z}
n = Θ(n log n)
| {z2 }
levels per level

2/21
Solving recurrences - three shapes

2T (n/2) + n2 2T (n/2) + n 2T (n/2) + 1

n2 n 1

n 2 n 2 n/2 n/2



2 2
1 1

.. .. ..
. . .

n2 2
n2 , 2
, n4 , . . . n, n, n, . . . 1, 2, 4, . . .

shrinks → root wins equal → nobody wins grows → leaves win

Θ(n2 ) Θ(n log n) Θ(n)

Same branching, different local work. These three pictures are the master theorem.

3/21
Solving recurrences - setting up the sum

nd level 0: 1 node

(n/b)d ··· (n/b)d level 1: a nodes

( bn2 )d ··· ··· ( bn2 )d level 2: a2 nodes

..
.

 n d logb n
j a X
level j = a = nd r j , r= d =⇒ T (n) = n d j
r
bj b
j=0

geometric series with ratio r ?

4/21
Solving recurrences - which shape are you in?

r <1 r =1 r >1
levels shrinking equal growing
dominated by the root nobody the leaves
condition a < bd a = bd a > bd
equivalently d > logb a d = logb a d < logb a
T (n) Θ(nd ) Θ(nd log n) Θ(nlogb a )

Geometric series: Θ(first term) / Θ(number of terms) / Θ(last term).

5/21
Solving recurrences - master theorem

For T (n) = a T (n/b) + Θ(nd ), compare d with logb a:




Θ(nd ) d > logb a

T (n) = Θ(nd log n) d = logb a



Θ(nlogb a ) d < logb a


nlogb a is the number of leaves. Root work vs. leaf work.

6/21
Solving recurrences - two families

√
Divide T (n/b) (a)–(f) Subtract T (n − 1), T ( n) (g)–(k)
Master theorem applies. Unroll and sum.

(a) Θ(nlog3 2 ) (d) Θ(n2 log n) (g) Θ(n) (j) Θ(2n )

(b) Θ(nlog4 5 ) (e) Θ(n3 log n) (h) Θ(nc+1 ) (k) Θ(log log n)
(c) Θ(n log n) (f) Θ(n3/2 log n) (i) Θ(c n )

7/21
Solving recurrences - two edge cases

(f) Driving term is not Θ(nd ) — sum the tree.

49 j
T (n) = 49 T (n/25) + n3/2 log n n3/2 log n


level j ≤ 125

Geometric, ratio < 1 ⇒ root dominates: Θ(n3/2 log n).

(k) Size shrinks by a root — change variable.

√ n=2m
T (n) = T ( n) + 1 −−−−→ S(m) = S(m/2) + 1 ⇒ Θ(log log n)

8/21
Fast Fourier transform - motivation

Goal: multiply two polynomials.

C (x) = A(x) · B(x), deg A, deg B < n
Naive way: convolve the coefficients,
X
ck = ai b j =⇒ Θ(n2 ) work.
i+j=k

Idea: change representation. Instead of coefficients, describe a polynomial by its

values at n points x0 , . . . , xn−1 :


A ←→ A(x0 ), . . . , A(xn−1 )
Then multiplication is just pointwise:
C (xi ) = A(xi ) · B(xi ) =⇒ Θ(n) work, once we have the values.

So which points xi should we evaluate at? 9/21

Fast Fourier transform - roots of unity 2.7

ω = e 2πi/n , roots = 1, ω, ω 2 , . . . , ω n−1

Sum (geometric series, n ≥ 2):

n−1
X ωn − 1
ωk = =0
ω−1
k=0

Product: 
n−1 +1
Y n odd
ω k = ω n(n−1)/2 = (−1)n−1 =
−1 n even
k=0

Sum = 0 is what makes the inverse transform work.

10/21
Fast Fourier transform - the roots, on the circle

For n = 4: ω = i, and the roots

i
1, ω, ω 2 , ω 3 = 1, i, −1, −i
90◦
sit at 90◦ apart on the unit circle.
−1 1
360◦
In general, the n-th roots are spaced
n
apart — equally spaced, which is exactly
−i
the symmetry behind

1 + ω + · · · + ω n−1 = 0.

11/21
Fast Fourier transform - why it’s fast: split by parity

Split the coefficients into even- and odd-indexed

halves: ..
.

A(x) = Ae (x 2 ) + x Ao (x 2 ) +1 −1 +i −i

Ae , Ao have degree < n/2. We need A at the n

+1 −1
points ω 0 , . . . , ω n−1 , so Ae , Ao are needed at the
squared points (ω k )2 . +1
Key fact: ω2 is a primitive (n/2)-th root of
unity, and (ω )2 = (ω k+n/2 )2 .
k Squaring walks roots down to ±1 — going
back up, each level is a choice of square
So the n squared points collapse onto only n/2 root.
distinct values.

T (n) = 2 T (n/2) + O(n) = O(n log n) 12/21

Fast Fourier transform - the transform 2.8

X
FFT(a0 , . . . , an−1 ) = A(ω 0 ), . . . , A(ω n−1 ) , aj x j


A(x) =
j

For n = 4: ω = i, powers (1, i, −1, −i). Inverse: use ω −1 , divide by n.

a FFT(a) a is the FFT of

1
(1, 0, 0, 0) (1, 1, 1, 1) 4 (1, 1, 1, 1)
1
(1, 0, 1, −1) (1, i, 3, −i) 4 (1, −i, 3, i)

Impulse ↔ flat. Coefficients ↔ values, in O(n log n).

13/21
Fast Fourier transform - evaluating directly on the circle

Take A(x) = 1 + x 2 − x 3 (coefficients

x = i : A(i) = i (1, 0, 1, −1)).
No recursion needed here — just plug in
each root directly:
A(−1) = 3 x = 1 : A(1) = 1
A(1) = 1 + 1 − 1 = 1

A(i) = 1 + i 2 − i 3 = 1 − 1 + i = i
A(−i) = −i
A(−1) = 1+1+1 = 3, A(−i) = 1−1−i = −i

So FFT(1, 0, 1, −1) = (1, i, 3, −i) — the

value representation.

14/21
Matrix multiplication - naive vs. the obvious block recursion

X
C = AB, cij = aik bkj =⇒ n3 scalar mults, O(n3 )
k

Block recursion (the obvious way):

" # " #" #
C11 C12 A11 A12 B11 B12
=
C21 C22 A21 A22 B21 B22

Each Cij = Ai1 B1j + Ai2 B2j needs 2 block products ⇒ 8 products of size n/2, plus
O(n2 ) adds.

T (n) = 8T (n/2) + O(n2 ) = O(n3 ) — no gain over naive.

15/21
Matrix multiplication - Strassen’s seven products

7 products (only +, −, no extra mults): Recombine into C :

M1 = (A11 + A22 )(B11 + B22 ) C11 = M1 + M4 − M5 + M7

M2 = (A21 + A22 ) B11 C12 = M3 + M5
M3 = A11 (B12 − B22 ) C21 = M2 + M4
M4 = A22 (B21 − B11 ) C22 = M1 − M2 + M3 + M6
M5 = (A11 + A12 ) B22 7 multiplications, 18 additions —
M6 = (A21 − A11 )(B11 + B12 )
trades 1 block mult for extra adds.
M7 = (A12 − A22 )(B21 + B22 )

T (n) = 7T (n/2) + O(n2 ) = O(nlog2 7 ) ≈ O(n2.807 )

T (n) = kT (n/2) + O(n2 ) =⇒ O(nlog2 k )
The exponent depends only on k, the number of block products. This is the lever part
(b) tries to pull — 5 instead of 7 — for squaring. 16/21
Matrix squaring - five products, and why they don’t recurse 2.27

" # " #
a b a 2 + bc b(a + d)
A= A2 =
c d c(a + d) d 2 + bc

Five products: a2 , d 2 , bc, b(a+d), c(a+d).

The recursion fails:

A11 A12 + A12 A22 ̸= A12 (A11 + A22 )

ab + bd = b(a + d) used commutativity. Matrices do not commute.

Also: A12 A21 is a product, not a square - nothing to recurse on.

17/21
Matrix squaring - squaring ≡ multiplying 2.27(c)

(A + B)2 = A2 + AB + BA + B 2 =⇒ AB + BA = (A + B)2 − A2 − B 2

Three squarings + O(n2 ).

Kill BA with a block embedding:

" # " # " #
X 0 0 Y 0 XY
A= , B= =⇒ AB + BA =
0 0 0 0 0 0

S(n) = O(nc ) =⇒ multiplication in O(nc )

18/21
Closest pair of points - the algorithm 2.32

1. Split at the median x into L and R.

2. Recurse; d = min(dL , dR ).
3. Keep the strip |xi − x| < d; sort it by y .
4. Compare each point with the next seven.
5. Best of the three candidate pairs.

Recursion handles L–L and R–R for free. All the work is in split pairs.

19/21
Closest pair of points - why seven

Packing lemma. A d × d square holds ≤ 4 points of L.

√
Quarter it: two points in one quarter would be ≤ d/ 2 < d apart.

Points between p and q in y -order lie in a 2d × d rectangle = two d × d squares ⇒

≤ 8 points ⇒ ≤ 6 in between.

T (n) = 2T (n/2) + O(n log n) = O(n log2 n)

pre-sort by y once =⇒ T (n) = 2T (n/2) + O(n) = O(n log n)

20/21
Polynomial interpolation - 2.10

n + 1 points determine a polynomial of degree ≤ n uniquely.

X Y x − xj
p(x) = yi (Lagrange)
xi − x j
i j̸=i

Shortcut here: p(3) = p(5) = 0 ⇒ p(x) = (x − 3)(x − 5) q(x), deg q = 2.

p(x) = − 34 x 4 + 25 3
3 x − 125 2
4 x + 137
3 x − 20

Read the data before choosing the method.

21/21