Exercise 2. FAST FOURIER TRANSFORM. The objective is to compute all the coefficients of the product

of two polynomials P and Q that are both of the generic form

where the pj's and qij's are given coefficients. One step in this procedure requires the computation of

P at the N2 points (wi,wi) for 0 ≤i, j≤N-1, where N is a power of two, and w = exp(2πi/N) is an

N-th root of unity. Taking inspiration from Tukey's solution, show how this can be done efficiently, derive

the recurrence for the RAM model complexity of your algorithm, and obtain the worst-case time in 0 ()

notation. Finally, without repeating the details, give the recurrence and its solution for the d-dimensional

version of this problem (i.e., replace (z,y) by a d-dimensional vector).