Confusion related to time complexity of fast fourier transform

Question

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

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