Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)

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




Solution

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


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More
Ask Your Question or Put Your Review.

loading...