Goertzel Algorithm - Computational Complexity

Computational Complexity

According to Computational complexity theory, computing a set of DFT terms using applications of the Goertzel algorithm on a data set with values with a "cost per operation" of has a complexity order

• To compute a single DFT bin for a complex input sequence of length, the Goertzel algorithm requires multiplications and additions/subtractions within the loop, as well as 4 multiplications and 4 final additions/subtractions, for a total of multiplications and additions/subtractions. This is repeated for each of the frequencies.

In contrast, using an FFT on a data set with values has a complexity order

• This is harder to apply directly because it depends on the FFT algorithm used, but a typical example is a radix-2 FFT, which requires multiplications and additions/subtractions per DFT bin, for each of the bins.

In the complexity order expressions, when the number of calculated terms is smaller than, the advantage of the Goertzel algorithm is clear. But because FFT code is comparatively very complex, the "cost per unit of work" factor is often much larger for an FFT, and the practical advantage favours the Goertzel algorithm more than the complexity expressions indicate.

As a rule-of-thumb for determining whether a radix-2 FFT or a Goertzel algorithm is more efficient, adjust the number of terms N in the data set upward to the nearest exact power of 2, calling this, and the Goertzel algorithm is likely to be faster if

FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work." FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage.

Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants specialised for transforming real-valued data.