Space-time trade-offs on the FFT algorithm
- 1 September 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 24 (5) , 563-568
- https://doi.org/10.1109/tit.1978.1055938
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.Keywords
This publication has 6 references indexed in Scilit:
- On Time Versus SpaceJournal of the ACM, 1977
- Big Omicron and big Omega and big ThetaACM SIGACT News, 1976
- Space bounds for a game on graphsPublished by Association for Computing Machinery (ACM) ,1976
- Efficient compilation of linear recursive programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- Historical notes on the fast Fourier transformProceedings of the IEEE, 1967
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965