Algorithms · Fourier analysis

DFT vs FFT cost

The direct DFT costs N² multiply–adds while the FFT costs N·log₂N, and racing both on the same 2,048 samples gives identical output with a measured speedup on this machine.

Taught in Sines & Spectra.

The chart plots N² against N·log₂N on logarithmic axes; the race button times the direct evaluation once and the FFT sixty times on the same random input, checks that the outputs match, and reports the speedup.

The claim above is what this widget demonstrates. Disagree with it?

Where next