UGC NET Computer Science December 2019 | Question 92

Question 92

---

The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is:

1. (1) θ(n lg n)
2. (2) θ(n²)
3. (3) θ(n)
4. (4) θ(lg n)

Answer : (1) θ(n lg n)

Explanation

To multiply two polynomials time complexity is θ(n²) but the time complexity to multiply two polynomials of degree n using Fast Fourier transform method is θ(n lg n)

So, option 1 is correct answer

Reference : Fast Fourier Transformation for poynomial multiplication

Previous	Next
UGC NET CS December 2019 - Question 91	UGC NET CS December 2019 - Question 93