# The Fast Fourier Transform

DevFeed: [The Fast Fourier Transform](<https://devfeed.tech/articles/the-fast-fourier-transform-40280.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/07/18/the-fast-fourier-transform/>)

Published: 2012-07-18T08:00:54Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [processing](<https://devfeed.tech/topics/processing.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [audio](<https://devfeed.tech/tags/audio.md>), [divide-and-conquer](<https://devfeed.tech/tags/divide-and-conquer.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [graphics](<https://devfeed.tech/tags/graphics.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [processing](<https://devfeed.tech/tags/processing.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [signal-processing](<https://devfeed.tech/tags/signal-processing.md>), [sound](<https://devfeed.tech/tags/sound.md>)

## AI overview

A tutorial on the Fast Fourier Transform explains its historical development, the improvement from O(n^2) to O(n log n) computation for the discrete Fourier transform, and a derivation and implementation approach. It also explores audio denoising by filtering a noisy signal's frequency spectrum.

## Source excerpt

It's often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey's paper, "An Algorithm for the Machine Calculation of Complex Fourier Series." They published a landmark algorithm which has since been called the Fast Fourier Transform algorithm, and has spawned countless variations. Specifically, it improved the best known computational bound on the discrete Fourier transform from $ O(n^2)$ to $ O(n \log n)$, which is the difference between uselessness and panacea.