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$.

Normally, multiplying two polynomials by the direct method takes:

$O(n^2)$

Using FFT, polynomial multiplication is done in three main steps:

Step 1: Convert coefficient form to point-value form using FFT.

Time complexity:

$O(n\log_2 n)$

Step 2: Multiply corresponding values.

Time complexity:

$O(n)$

Step 3: Convert point-value form back to coefficient form using inverse FFT.

Time complexity:

$O(n\log_2 n)$

Total time complexity:

$O(n\log_2 n)+O(n)+O(n\log_2 n)$

$=O(n\log_2 n)$