Here are a few hints, then the solution.
1 -
First of all, you should make sure that you can perform the multiplication in less than n^2 coefficient multiplications, on a simple example :
(aX + b)*(cX + d)
One of your multiplications should be (a+b)*(c+d)
2 -
Haven't found how to do it ?
Here are the operations for each power :
X^2 : ac
X : (a+b)*(c+d) - ac - bd
1 : bd
You just have to perform 3 multiplications instead of 4. Additions do not cost that much compared to multiplications.
3 -
You are asked to find a solution in Theta(n^lg(3)). Here is a quick reminder of the 'Théorème Général' :
Let T(n) the cost of your algorithme for the polynoms with degree n.
With a 'divide to conquer strategy' which leads to :
T(n) = aT(n/b)+f(n)
If f(n)~O(n^lg_b(a)) then T(n) = Theta(n^lg_b(a))
You are looking for T(n) = Theta(n^lg_2(3)). This could mean that :
T(n)=3.T(n/2) + epsilon
If you split your polynoms in even and odd polynoms, they have half of the initial coefficients amount : n/2.
The formula shows you that you will perform three multiplications between the odd and even polynoms...
4 -
Consider to represent your polynom P(x) with degree n this way :
P(X) = X.A(X) + B(X)
A(X) and B(X) contain n/2 coefficients.
5 - Solution
P(X) = X.A(X) + B(X)
P'(X) = X.A'(X) + B'(X)
The coefficients of P*P'(X) is the sum of the coefficients of :
X^2.A.A'
X.(A.B'+A'.B) = X.[(A+B)(A'+B') - A.A' - B.B']
B.B'
So you have to call your multiplication algorithm on :
A and A'
A+B and A'+B'
B and B'
Then you can recombine coefficients with shifts and additions.
Cheers