Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Jacques Morgenstern · Journal of the ACM · 1973
A lower bound for the number of additions necessary to compute a family of linear functions by a linear algorithm is given when an upper bound c can be assigned to the modulus of the complex numbers involved in the computation. In the case of the fast Fourier transform, the lower bound is ( n /2) log 2 n when c = 1.