Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Author:
Open Access
- 1 April 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 20 (2) , 305-306
Abstract
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.Keywords
This publication has 1 reference indexed in Scilit:
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965