4 [5 5-25 points! You are given n = 2k polynomials n-1 of degree n 1 each. The complex coefficients aij are represented by pairs of floating point numbers. You are also given a table with l,w,w1.... ,, where w is the priivn-th root of unity e2 Now assume, you want to compute the product of these n polynomi- als A) . P . . Pn-1. We count each arithmetic operation on real numbers as 1 step, even though one should actually worry whether multi-precision arithmetic is needed for large n. For each answer give just enough justification, to show how you com- puted your answer (a) Assume, you compute the product from left to right with school multiplication (brute fo). What is the asymptotic running time? (b) Assume, you compute the product Po. .. P-1 in a more clever balanced way. How? (Just tel which product is computed last.) What is the asymptotic running time with school multiplication (brute force)? (c) Assume, you use the same organization as in (b), but you employ FFT (Fast Fourier Transform) for each multiplication. What is the asymptotic running time now? (d) In (c), you do every multiplication with the help of 2 FFT's and lnverse FFT. You notice that all but the last inverse FFT is immediately followed by an FFT. Why does this make sense? (One might think, they just cancel each other.) (e) Now try to compute the same product by just n FFT's and 1 inverse FFT. The computation in between consists entirely of multiplications of values. What is the asymptotic running time now? 4 [5 5-25 points! You are given n = 2k polynomials n-1 of degree n 1 each. The complex coefficients aij are represented by pairs of floating point numbers. You are also given a table with l,w,w1.... ,, where w is the priivn-th root of unity e2 Now assume, you want to compute the product of these n polynomi- als A) . P . . Pn-1. We count each arithmetic operation on real numbers as 1 step, even though one should actually worry whether multi-precision arithmetic is needed for large n. For each answer give just enough justification, to show how you com- puted your answer (a) Assume, you compute the product from left to right with school multiplication (brute fo). What is the asymptotic running time? (b) Assume, you compute the product Po. .. P-1 in a more clever balanced way. How? (Just tel which product is computed last.) What is the asymptotic running time with school multiplication (brute force)? (c) Assume, you use the same organization as in (b), but you employ FFT (Fast Fourier Transform) for each multiplication. What is the asymptotic running time now? (d) In (c), you do every multiplication with the help of 2 FFT's and lnverse FFT. You notice that all but the last inverse FFT is immediately followed by an FFT. Why does this make sense? (One might think, they just cancel each other.) (e) Now try to compute the same product by just n FFT's and 1 inverse FFT. The computation in between consists entirely of multiplications of values. What is the asymptotic running time now