DescriptionThe Cooley-Tukey algorithm, published by James Cooley and John Tukey in 1965 (though a similar method was devised by Carl Friedrich Gauss around 1805 and unpublished for over a century), reduces the cost of computing a discrete Fourier transform from O(n^2) direct evaluation to O(n log n), one of the most widely used algorithms in computing, underlying digital signal processing, image compression, and large-integer multiplication. Its O(n log n) complexity remains the practical standard nearly 60 years later; whether an asymptotically faster general DFT algorithm is possible remains a formally open question in complexity theory.
Formal questionThe Cooley-Tukey fast Fourier transform algorithm computes the discrete Fourier transform of a length-n sequence in O(n log n) arithmetic operations, versus O(n^2) for direct evaluation of the defining sum, remaining the standard general-purpose FFT algorithm complexity in practical use as of 2026, though a matching unconditional lower bound proving no faster general algorithm can exist remains an open theoretical question.
Scope auditDoes your result fit this record?
Change a parameter to stress-test whether a proposed result is still inside the published specification. This is an audit aid, not a proof checker.
This record has no editable parameters. Read the formal question and assumptions before challenging it.
Scope matches the published specificationNo parameters changed
