Given the FFT we can have time procedure for multiplying two polynomials A(x)…
2022
Given the FFT we can have time procedure for multiplying two polynomials A(x) and B(x) of degree bound n where input and output representations are in coefficient form, assuming n is a power of 2.
- A.
\(O\left(\mathrm{n}^{2}\right)\) - B.
\(O\left(n \cdot \log _{2} n\right)\) - C.
\(\mathrm{O}\left(2^{\mathrm{n}}\right)\) - D.
\(\mathrm{O}\left(\log _{2} \mathrm{n}\right)\)
Attempted by 22 students.
Show answer & explanation
Correct answer: B
Solution outline: multiply two polynomials using the FFT and derive the running time.
Step 1: Choose N = 2n (a power of two). If n is already a power of two, N = 2n works and is Θ(n). This ensures space for the full product of degree < 2n.
Step 2: Pad the coefficient vectors of both polynomials to length N by appending zeros.
Step 3: Compute the discrete Fourier transform (DFT) of both padded vectors at the N-th roots of unity using the FFT algorithm. Each FFT takes O(N log N) time.
Step 4: Multiply the two resulting value vectors pointwise. This requires N multiplications and takes O(N) time.
Step 5: Apply the inverse FFT to the pointwise product to recover the coefficient representation of the product polynomial. The inverse FFT also takes O(N log N) time.
Step 6: If necessary, trim any trailing zeros to obtain the final coefficients of degree < 2n.
Time complexity analysis: the dominant costs are the two FFTs and the inverse FFT: O(N log N) + O(N) + O(N log N) = O(N log N). Since N = Θ(n) (for the chosen N = 2n), the total time is O(n log n).
Final conclusion: the FFT-based polynomial multiplication runs in O(n log n) time under the given assumptions.
Remarks: Ensure n is a power of two as stated; otherwise pick N as the next power of two ≥ 2n, and the bound remains O(N log N) = O(n log n).
A video solution is available for this question — log in and enroll to watch it.