polynomials \[ f(x) = A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1} \] roots \begin{eqnarray} x^{n} &=& 1 \\\ x &=& e^{i \frac{2\pi}{n}} \end{eqnarray} Call \(e^{i \frac{2\pi}{n}} = w_n\) the fundamental, then there are \(n\) such roots, \(w_n^k\) for \(k = 0,\cdots,n-1\). The fourier transform is a vector of the polynomial evaluated at each of the \(k\) roots. \[ F(k) = f(w_n^k) \] The FFT is a divide and conquer algorithm where instead of doing \(O(n)\) computations for each fourier coefficient \(F(k)\), we break up the problem into 2 subproblems of size \(n/2\) and do a merge which is of order \(n\).