I think the replies to this post are getting confused between the FFT/DFT, which is O(n log n), and the "naive Fourier transform", O(n2).

My experience with numerics in regular python is that they're generally 50-500x slower than the equivalent in C/C++, this just pushes back the point at which the asymptotics take over.