Confusion related to time complexity of fast fourier transform
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&lt; 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)$.