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


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

  • $\begingroup$ @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? $\endgroup$
    – user34790
    Feb 24, 2013 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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