COMPSCI 330: Design and Analysis of Algorithms Spring 2019
Lecture 3: Divide and Conquer
Lecturer: Rong Ge Scribe: Shweta Patwa
3.1 Integer multiplication
Input: Two positive n digit integers, a and b.
Output: a ∗ b
The naive approach is to simply multiply the two numbers which takes O(n2 ) time because we need to
multiply each digit in one number with those in the second number, put them in the correct position and
add them as shown below.
38 4
×
5 6
230 4
1920
2150 4
Can we do better?
Suppose we are given a = 123456 and b = 654321. We can rewrite a as 123000 + 456 and b as 654000 + 321.
As a result, a ∗ b = 123 ∗ 654 ∗ 106 + (123 ∗ 321 + 456 ∗ 654) ∗ 103 + 456 ∗ 321.
Assume n is a power of 2. We partition a and b into lower and upper digits as a = a1 ∗ 10n/2 + a2 and
b = b1 ∗ 10n/2 + b2 . Thus, the product becomes A ∗ 10n + (B + C) ∗ 103 + D, where A = a1 ∗ b1, B =
a2 ∗ b1, C = a1 ∗ b2 and D = a2 ∗ b2.
Recursion: Let T (n) be the running time to multiply two n-digit numbers, a and b.
M ultiply(a, b):
1. WLOG assume n = length(a) = length(b), can pad 0’s for shorter number
2. if length(a) <= 1 then return a ∗ b
3. Partition a,b into a = a1 ∗ 10n/2 + a2 and b = b1 ∗ 10n/2 + b2
4. A = M ultiply(a1, b1)
5. B = M ultiply(a2, b1)
6. C = M ultiply(a1, b2)
7. D = M ultiply(a2, b2)
8. Return A ∗ 10n + (B + C) ∗ 10n/2 + D
Thus,
n
T (n) = 4T ( ) + O(n)
2
3-1
3-2 Lecture 3: Divide and Conquer
where O(n) accounts for partitioning the given numbers, the addition operation(s) and shifting/padding.
We call this the ‘merge’ time.
T (n) = 4T (n/2) + A ∗ n (A*n indicates the merging cost at layer 0)
= 16T (n/4) + 4 ∗ A ∗ n/2 + A ∗ n
= 64T (n/8) + 16 ∗ A ∗ n/4 + 4 ∗ A ∗ n/2 + A ∗ n
We can assume T (1) = 1 since we are doing asymptotic analysis. Overall cost of the function is the sum of
the merging cost of all layers. The number of layers l = log2 n.
log2 n
X n
T (n) = 4i A
i=0
2i
log2 n
X
= An 2i
i=0
= An(2n − 1) = O(n2 )
3.2 Improved algorithm
We can improve the algorithm by doing one of the following:
1. Merging faster: However, this is not the bottleneck for integer multiplication. O(n) is not large.
2. Make subproblems smaller: If we do this naively, then that would result in more number of subproblems
which defeats the purpose.
3. Decrease the number of subproblem: We see the details below.
M ultiply(a, b) :
1. WLOG assume n = length(a) = length(b), can pad 0’s for shorter number
Lecture 3: Divide and Conquer 3-3
2. if length(a) <= 1 then return a ∗ b
3. Partition a,b into a = a1 ∗ 10n/2 + a2 and b = b1 ∗ 10n/2 + b2
4. A = M ultiply(a1, b1)
5. B = M ultiply(a2, b2)
6. C = M ultiply(a1 + a1, b1 + b2)
7. Return A ∗ 10n + (C − A − B) ∗ 10n/2 + B
Thus,
n
T (n) = 3T ( ) + O(n)
2
log2 n
X n
T (n) = 3i A
i=0
2i
log2 n
X 3
= An ( )i
i=0
2
(3/2)log2 n+1 − 1
= An
3/2 − 1
3 log2 n
= O(n )
2
log2 3/2
= O(n ∗ n )
= O(nlog2 3 )
= O(n1.585 )
Even faster algorithms use fast Fourier analysis, which is beyond the scope of this class.
3.3 Master theorem
The Master Theorem acts as a ”cheat sheet” for basic recursions. Given T (n) = aT ( nb ) + f (n)):
