# Historically are there any documented attempts at finding algorithms that are asymptotically faster than the FFT for the Discrete Fourier Transform?

I found out some bounds on the Discrete Fourier Transform calculation on certain models of computation but nothing on attempts at finding algorithms asymptotically faster than the Cooley-Tukey FFT on the RAM model of computation. The Discrete Fourier Transform can be defined as follows: Given a sequence $$x_0,x_2..,x_{N-1}$$ of $$N$$ complex numbers transform them into $$X_0,..,X_{N-1}$$ with: $$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi \tfrac{k}{N}n}$$

Historically are there any documented attempts at finding algorithms that are asymptotically faster than the FFT for the Discrete Fourier Transform?

• Reversing, the question, why would you expect there to be any? Outside of specific restricted inputs, such as sparse data, O(N log N) looks to be already optimal. We have n input values to turn into n output values, where every output depends on every input in a reversible fashion. Calculating any single of them already takes N operations, so getting the rest for only O(log N) times that already sounds like a bargain to me. Also, as memory is limited, for any practical problem, log N is just a multiplicative constant and the question rather boils down to which is the faster implementation.
– mlk
Commented Jun 27 at 12:46
• @mlk Since there isn't any proof that no linear time algorithm is obtainable and given that the dft has several important applications I would assume that some scientists have tried to obtain a linear algorithm or at least a proof that such algorithm doesn't exist in general RAM setting lets say. Commented Jun 27 at 14:05

Let $$s$$ be the number of samples and $$k$$ be the $$k$$-sparcity of the spectrum, then the runtime is $$O(k \log s)$$, which for fixed $$k < s$$ is sub-linear. While sublinear performance is asymptotically better than the FFT's asymptotic runtime of $$O(n\log n)$$ it is not a straight-up general improvement due to the sparsity requirement.