(4) Given two real polynomials P (x), Q(x) of the same degree n, which is a power of two: n = 2i, we want to multiply them using less than (n2) multiplications of coefficients. To begin with, we can write

P(x) = A0(x)+A1(x)xn2 and Q(x) = B0(x)+B1(x)xn2 , where A1(x) and B1(x) have degree n2 and A0(x) and B0(x) have degree n 1.

2 234 22

(Forexample,1+10x+6x 4x +x =(1+10x)+(64x+5x )x .) We can find P(x)Q(x) using only 3 multiplications of polynomials, instead of the usual 4:

2

First multiplication: (A0(x) + A1(x))(B0(x) + B1(x)); Second multiplication: A0(x)B0(x); Third multiplication: A1(x)B1(x). (i) Explain why these 3 multiplications are sufficient to find P (x)Q(x)

(ii) Let T (n) be the number of multiplications of coefficients needed to multiply two polynomials with degrees less than or equal to n. Use part (i) to write a recursion of the form

n T(n)=aT b +f(n),

using the fact that the addition of two polynomials with degrees less than or equal to n is O(n). (iii) Use the master theorem to solve the recursion in (ii).