DocumentCode :
929076
Title :
Space-time trade-offs on the FFT algorithm
Author :
Savage, John E. ; Swamy, Sowmitri
Volume :
24
Issue :
5
fYear :
1978
fDate :
9/1/1978 12:00:00 AM
Firstpage :
563
Lastpage :
568
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 with 
inputs, as a power of two, is implemented with 
temporary locations where 
, then the computation time 
grows faster than 
. Furthermore, can grow as fast as 
if 
where 
, the minimum necessary. These results are obtained by deriving tight bounds on versus and .
inputs, as a power of two, is implemented with temporary locations where , then the computation time grows faster than . Furthermore, can grow as fast as if where , the minimum necessary. These results are obtained by deriving tight bounds on versus and .Keywords :
DFT; Discrete Fourier transforms (DFT´s); Graph theory; Algorithm design and analysis; Batteries; Computer science; Discrete Fourier transforms; Extraterrestrial measurements; Fast Fourier transforms; Helium; History; Signal processing algorithms; Time measurement;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1978.1055938
Filename :
1055938
Link To Document :
