The naive implementation of the DFT in terms of a matrix-vector multiplication has time complexity O(n^2) [1]. The point is that the FFT approach is much faste

The naive implementation of the DFT in terms of a matrix-vector multiplication has time complexity O(n^2) [1]. The point is that the FFT approach is much faster than that implementation. [1] https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix