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