Q14.Marks: +2.0UGC NET Paper 2: Computer Science 11 March 2023
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.
1.O(n2)
2.O(n.log2n)✓ Correct
3.O(2n)
4.O(log2n)
Solution
The correct answer is O(n.log2n)
Key Points
The classical procedure for polynomial multiplication results in an O(n2) time complexity. This is because you are doing a pairwise multiplication of each coefficient from the first polynomial with each coefficient of the second polynomial. If both polynomials have n terms, that's n times n, which results in the O(n2) complexity.
However, the Fast Fourier Transform (FFT) can help us improve this. Here is a high level process of polynomial multiplication using FFT:
Convert the two polynomials from coefficient form to point-value form. For a polynomial of degree bound n, we want to evaluate it at n distinct points. This requires O(n log n) operations using the FFT.
Now that we have the same set of n points for the two polynomials, we multiply the corresponding values together. That's just n multiplications O(n).
Finally, we convert the resulting points back to the coefficient form using the Inverse FFT (again, O(n log n) operations).
Adding all these up, we get O(n log n) + O(n) + O(n log n) = O(n log n) as dominant term which is significantly faster than O(n2).
This improvement is substantial: a problem that would be computationally infeasible with the classical method may be feasible with the FFT-based method.
