Question

Polynomial Multiplication by Divide-&-Conquer

A degree n-1 polynomial ? (?) =Σ(n-1)(i=0) ???ⁱ = ?0 + ?1? + ?2?² ... + ??−1?^n-1 can be

represented by an array ?[0. . ? − 1] of its n coefficients. Suppose P(x) and Q(x) are two polynomials of degree n-1, each given by its coefficient array representation. Their product P(x)Q(x) is a polynomial of degree 2(n-1), and hence can be represented by its coefficient array of length 2n-1. The polynomial multiplication problem is to compute the coefficient array of P(x)Q(x), given the coefficient arrays of P(x) and of Q(x).

There is an obvious Θ ?2 (i.e., quadratic) time algorithm to solve this problem. However, a method similar to the divide-&-conquer integer multiplication algorithm of Karatsuba-Ofman can achieve sub-quadratic time complexity. Design and analyze one such sub-quadratic algorithm for the polynomial multiplication problem.

Answer 1

Running Time For Following Algorithm Is wich is Better

PolyMulti(P(x),(x))

begin

end

Thus as you can see from above steps and process that it need to call recursive multiplication procedure three times rather than four times

Hence

RUNNING TIME OF ALGORITHM WILL BE REDUCED TO .... Given in above image

**** HELLO I HAVE ADDED MORE DETAILS AS YOU REQUERED PLEASE REPLACE A WITH P AND B WITH Q AS PER YOUR REQUIREMENTS****

****THANK YOU****