UGCNET CSE December 2022: 27

Question

 

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

1. $O\left(\mathrm{n}^{2}\right)$
2. $O\left(n \cdot \log _{2} n\right)$
3. $\mathrm{O}\left(2^{\mathrm{n}}\right)$
4. $\mathrm{O}\left(\log _{2} \mathrm{n}\right)$

(Option $1[39405]) 1$
(Option $2 [39406]) 2$
(Option $3 [39407]) 3$
(Option $4 [39408]) 4$

Answer Given by Candidate : $3$

Answer 1

The correct answer is $O(n * log₂ n)$.

The FFT is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse, in a much more efficient way than directly computing it by definition. When used for polynomial multiplication, the FFT can compute the product of two polynomials of degree-bound n in $O(n * log₂ n)$ time. This is significantly faster than the naive approach, which takes $O(n²)$ time.

The FFT-based method works by representing the polynomials in the point-value form, performing point-wise multiplication of the values, and then converting back to the coefficient form. This process is much faster than directly multiplying the coefficients of the polynomials.