notes

n-1 2. Given two polynomials of degree n-1: A()nd B(r)br. The product of these two polynomials is another polynomial C() of degree up to 2n -2 given by 2n-2 i- n-1 For this problem, we are given the coefficients for A(x)- aiz' and Bla) biz' as two arrays Al0,.,n-1ao.a- and B(O,.,n-1bbn-, respectively. We want to compute the product C(z) := A(r)B(z) and return the coefficient lists C(. . . . , 2n 2] = [co, . . . , c 2n-2] For all parts, you are not required to prove correctness of your algorithms, but are required to give a time analysis in O form. (a) (5 points) Give the straight-forward, iterative algorithm for this problem. (b) (10 points) Give a simple divide-and-conquer algorithm for this problem (c) (10 points) Use the Karatsuba method to give an improved divide-and-conquer algorithm for this