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