Page "Fast Fourier transform" Paragraph 23

A tight lower bound is not known on the number of required additions, although lower bounds have been proved under some restrictive assumptions on the algorithms.

In 1973, Morgenstern proved an lower bound on the addition count for algorithms where the multiplicative constants have bounded magnitudes ( which is true for most but not all FFT algorithms ).

Pan ( 1986 ) proved an lower bound assuming a bound on a measure of the FFT algorithm's " asynchronicity ", but the generality of this assumption is unclear.

For the case of power-of-two, Papadimitriou ( 1979 ) argued that the number of complex-number additions achieved by Cooley – Tukey algorithms is optimal under certain assumptions on the graph of the algorithm ( his assumptions imply, among other things, that no additive identities in the roots of unity are exploited ).

( This argument would imply that at least real additions are required, although this is not a tight bound because extra additions are required as part of complex-number multiplications.

) Thus far, no published FFT algorithm has achieved fewer than complex-number additions ( or their equivalent ) for power-of-two.