Given the FFT we can have ______ time procedure for multiplying two polynomials A(x) Q and B(x) of degree bound n where input and output representations are in coefficient form, assuming n is a power of 2.

1. AO(n²)
2. BO(n log₂ n)
3. CO(2ⁿ)
4. DO(log₂ n)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. O(n log₂ n)

Explanation

Evaluate both polynomials at 2n points with FFT, multiply pointwise, and interpolate with the inverse FFT: O(n log n) in total.