Complexity of the fast Fourier transform
Can the discrete Fourier transform of n values be computed with asymptotically fewer than n log n arithmetic operations?
Summary
All known fast Fourier transform algorithms, popularised by Cooley and Tukey in 1965, use O(n log n) operations, and no proof is known that fewer is impossible, even for lengths that are powers of two. Lower bounds of order n log n are known only under restrictions, such as Morgenstern’s 1973 bound on additions for algorithms with bounded constants.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.