Prefer a chat interface with context about you and your work?
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
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 …