Fast Fourier Transform

Almost everything you hear, see, or transmit is secretly a sum of simple waves. A chord is a few pure tones stacked together; a photo is a landscape of light and dark ripples; a Wi-Fi packet is a comb of carefully chosen frequencies. The Fourier transform is the lens that pulls a signal apart into those pure waves and tells you how much of each one is present.

The catch is cost. Doing it the obvious way — the discrete Fourier transform (DFT) — compares the signal against every frequency, one sample at a time. For $n$ samples that is on the order of $n^{2}$ multiplications. Double the data and the work quadruples. At a million samples that is a trillion operations, and the whole idea collapses under its own weight.

Then, in 1965, James Cooley and John Tukey published a way to do exactly the same computation in $n \log n$ steps. That gap — $n^{2}$ versus $n \log n$ — is the difference between "impossible on real data" and "runs in milliseconds on your phone." This is the story of that trick.

Below is a signal of n = 8 samples built by adding a few pure waves. Press Run FFT and the algorithm splits the data in half again and again, then recombines the pieces with butterfly steps to reveal exactly which frequencies are inside.

<p class="hint">{{hint}}</p>
<div class="panel">
  <div class="col">
    <div class="lbl">{{lbl_signal}}</div>
    <div id="signal" class="bars sig"></div>
  </div>
  <div class="col">
    <div class="lbl">{{lbl_freqs}}</div>
    <div id="spectrum" class="bars spec"></div>
  </div>
</div>
<div class="counts">
  <span class="chip naive">{{naive_chip}}</span>
  <span class="chip fast">{{fft_chip}}</span>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_new}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.panel { display: flex; gap: 1.2rem; flex-wrap: wrap; }
.col { flex: 1; min-width: 180px; }
.lbl { font-size: .8rem; font-weight: 600; color: #1d3557; margin-bottom: .3rem; }
.bars { display: flex; align-items: flex-end; gap: 4px; height: 120px;
        background: #f3f6f9; border: 1px solid #cdd9e3; border-radius: 8px; padding: 6px; }
.bars .bar { flex: 1; border-radius: 3px 3px 0 0; transition: height .25s ease; min-height: 2px; }
.sig .bar { background: #1d3557; }
.spec .bar { background: #c9ccd1; }
.spec .bar.hot { background: #e63946; }
.counts { display: flex; gap: .6rem; margin: .8rem 0 .3rem; flex-wrap: wrap; }
.chip { font-size: .85rem; font-weight: 600; padding: .3rem .65rem; border-radius: 999px; border: 1px solid; }
.chip.naive { color: #c92f3c; border-color: #e8b3b8; background: #fdf0f1; }
.chip.fast { color: #0a7d33; border-color: #b3ddc1; background: #eef9f1; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the two counters. The naive DFT does about $n^{2}$ operations; the FFT does about $n \log n$. At n = 8 that is 64 versus 24 — a modest win. But the gap is multiplicative: at n = 1024 it is roughly a million versus ten thousand, a hundredfold speedup, and it only widens from there. Both methods return the same frequencies — the FFT just refuses to do redundant work.

What exactly did Cooley and Tukey buy us? Not a different answer — the same frequencies, computed in a radically cheaper way.

• The naive DFT is $\Theta(n^2)$. Each of the $n$ output frequencies is a weighted sum over all $n$ inputs, so you pay $n \times n$ multiplications. This is correct and simple, but hopeless at scale.
• The FFT is $\Theta(n \log n)$. Split the samples into evens and odds, transform each half, and stitch the results together with cheap butterfly combinations. The same half-transforms feed both halves of the output, so the redundant work the DFT repeats is done exactly once.
• The recursion is the magic. You halve the problem $\log n$ times, doing $\Theta(n)$ work per level — the textbook divide-and-conquer recurrence $T(n) = 2 \cdot T(n/2) + \Theta(n)$, the same shape behind fast multiplication and merge sort.
• Status: solved, and essentially optimal in practice. Cooley and Tukey published it in 1965, though Gauss had the core idea in 1805, before Fourier's own work. No asymptotically faster general method is known or expected, and the IEEE later named it one of the top algorithms of the 20th century.

So the FFT is not an open question or a hard barrier — it is a triumph. It is what $n \log n$ looks like when it rescues an $n^{2}$ problem that the world genuinely needs to solve, all the time.

The FFT is one of the most-used algorithms on Earth, hiding inside hardware and software you touch every day:

• Audio and images: MP3, JPEG and almost every codec work in the frequency domain to throw away what the ear and eye can't notice — only the FFT makes that fast enough for real time.
• Wireless: Wi-Fi, 4G and 5G send data across hundreds of frequencies at once (OFDM); every packet is assembled and decoded with an FFT.
• Science and medicine: MRI scanners, radio telescopes and seismographs all reconstruct their pictures of the world by transforming raw measurements into frequencies.
• Fast multiplication: multiplying enormous numbers or polynomials becomes cheap by moving to the frequency domain — the bridge to fast multiplication and large-integer arithmetic.

Whenever an algorithm needs to know which frequencies are present — and to know it quickly — the FFT is doing the heavy lifting. It is the quiet $n \log n$ engine under a startling amount of modern technology.

The Fourier transform was always a beautiful idea: every signal is a chord of pure waves. What it lacked was speed. The $n^{2}$ DFT was correct and useless on real data — until a single observation, that the even and odd samples share their work, dropped the cost to $n \log n$.

That is the whole lesson of complexity in one algorithm. The problem didn't get easier; the method got smarter, and a multiplicative speedup turned an impossible computation into a routine one. The next time your phone plays a song, cleans up a photo, or pulls a call out of the air, a tiny lattice of butterflies is running — quietly proving that the right algorithm can be the difference between $n^{2}$ and changing the world. For more on that same recursion, see fast multiplication.