On the real complexity of a complex DFT
Igor' Sergeevich Sergeev · Problems of Information Transmission · 2016
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 log2 N real operations of addition, subtraction, and scalar multiplication.