FFT's are fast DFT Algorithms.: "For example, the popular 'Radix 2' algorithms are useful if N is a regular power of 2 (N=2p). These algorithms have complexity of only O(N.logN). If we (naively) assume that algorithmic complexity provides a direct measure of execution time (and that the relevant logarithm base is 2) then the ratio of execution times for the (DFT) vs. (Radix 2 FFT) can be expressed:"
'via Blog this'