 Cooley–Tukey FFT algorithm

The Cooley–Tukey FFT algorithm is an efficient computational method for calculating the discrete Fourier transform (DFT) and its inverse. The DFT converts a sequence of complex numbers into another sequence of complex numbers, representing the frequency domain of the input signal. The direct computation of the DFT using its mathematical definition requires \(O(N^2)\) operations for \(N\) input points, which is computationally expensive for large datasets.