The time complexity to multiply two polynomials of degree 𝑛 using Fast…

Answer: θ(n log n)

Explanation:

• Pad the two coefficient sequences to length N, where N is a power of two at least 2n+1. This ensures N = Θ(n).

• Compute the FFT of both sequences. Each FFT takes O(N log N), so two FFTs cost O(N log N).

• Multiply the transformed values pointwise. This step is O(N).

• Compute the inverse FFT to interpolate the product coefficients. This is another O(N log N) step.

• Total time: O(N log N) + O(N) = O(N log N). Since N = Θ(n), the complexity is Θ(n log n).

Note: The naive coefficient-by-coefficient multiplication takes Θ(n^2), so the FFT-based method gives a substantial improvement for large n.