Space-time trade-offs on the FFT algorithm

Abstract

The performance of the fast Fourier transfmm algorithm is examined under limitations on computational space and time. It is shown that if the algorithm withninputs,nas a power of two, is implemented withStemporary locations whereS=o(n/ \log n), then the computation timeTgrows faster thann \log n. Furthermore,Tcan grow as fast asn^{2}ifS=S_{min} + O(1)whereS_{min}=l+\log_{2}n, the minimum necessary. These results are obtained by deriving tight bounds onTversusSandn.