It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform has a complexity $O(p\log p)$? since it would also involve solving module equations involving $p$ and $N$?
Thanks for any helpful answers.