We need an efficient way to multiply two integers. The widely used algorithm costs O(n²) time.
Our goal: improve on this quadratic running time.
The basic idea is to break up the product into partial sums.
The recurrence relation of the algorithm after some analysis: T(n) ≤ 3T(n/2) + cn
Algorithm
Recursive-Multiply(x,y):
Write x = x1*2^(n/2) + x0
y = y1*2^(n/2) + y0
Compute x1 + x0 and y1 + y0
p = Recursive-Multiply(x1 + x0,y1 + y0)
x1 y1 = Recursive-Multiply(x1,y1)
x0y0 = Recursive-Multiply(x0,y0)
Return x1y1.(2^n) + (p - x1y1 -
x0y0).(2^n/2) + x0 y0
Upon analyzing this algorithm, we find out that the overall running time is O(n^(log(base 3)3)= O(n^1.59).
I give this section 8/10