On the real complexity of a complex DFT

We present a method to construct a theoretically fast algorithm for computing the discrete Fourier transform (DFT) of order $N=2^n$. We show that the DFT of a complex vector of length $N$ is performed with complexity of $3{,}76875N\log_2N$ real operations of addition, subtraction, and scalar multiplication.