Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.

It says that lets say I have a polynomial of degree n-1. I want to evaluate the polynomial at $2n^{th}$ roots of unity. For that I can use divide and conquer rule

I will divide my polynomial into evens and odds i.e,

$A(x) = A_{even}(x^2) + xA_{odd}(x^2)$

Now if I want to evaluate A at one of the $2n^{th}$ roots of unity. I can break it into evaluating the $n^{th}$ root of unity at two polynomials $A_{even}$ and $A_{odd}$ and then add the results with complexity O(n).

They have shown the results to be O(nlogn). However, I think this is for evaluating the value of the polynomial at one of the roots not all the $2n^{th}$. But the book seems to say it is the total complexity. I am a bit confused.

Can anyone please explain this to me? I am confused

share|improve this question
add comment

1 Answer 1

If you compute by recursion each unit root at a time, it will indeed be costly. However, observe that when you compute $A_{even}(\omega_{n/2}^i)$ and $A_{odd}(\omega_{n/2}^i)$, you actually gain two values for $A$. For $i< n/2$ we have that:

$A(\omega^i_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^i\cdot A_{odd}(\omega_{n/2}^i)$

$A(\omega^{i+n/2}_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^{i+n/2}\cdot A_{odd}(\omega_{n/2}^i)$

This ability to compute two values using a single computation of $A_{even}$ and $A_{odd}$ allows for the divide and conquer approach to reduce the time to $O(n\log n)$.

share|improve this answer
    
@Shauli. I didn't get it. As you said ok assume that for calculating for two values of unit roots we use single computation of $A_{even}$ and $A_{odd}$. But for calculating lets say 2n values we still need n computations each of time O(nlogn) so the total time will still be $O(n^2logn)$ isn't it? –  user34790 Feb 24 '13 at 9:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.