To evaluate the estimator (8 .20) for the power spectrum, it is necessary to perform N multiplication operations for each frequency, and the variance spectrum can be evaluated at Ndifferent frequencies, so of order N2 multiplications are needed. If there are 512 points in the time series, 262,144 multiplications are needed; for 1024 points, more than 1,000,000 multiplications must be performed to evaluate the variance spectrum. The number of multiplications required to estimate the autocovariance function is of the same order.
The fast Fourier transform (or FFT) provides a much faster way to perform the calculations. In the FFT, the arguments that appear repeatedly in (8.20) are consolidated to decrease the number of operations needed to evaluate the Fourier transform. The FFT is exactly equivalent to conventional evaluation of the Fourier coefficients, but provides substantial savings in computer time for long time series. Computer routines to calculate the FFT are commonly available in software packages; see, e.g., Press et al. (1992) p. 496.