Introduction

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 nn samples that is on the order of n2n^{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 nlog⁡nn \log n steps. That gap — n2n^{2} versus nlog⁡nn \log n — is the difference between "impossible on real data" and "runs in milliseconds on your phone." This is the story of that trick.

Decompose a Signal

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">This signal of 8 samples is built from a few pure waves. Press
<b>Run FFT</b> to split it in half again and again and recombine with
<b>butterfly</b> steps — the bars show how much of each frequency it found. Same
answer as the naive transform, far fewer operations.</p>
<div class="panel">
  <div class="col">
    <div class="lbl">Signal (8 samples)</div>
    <div id="signal" class="bars sig"></div>
  </div>
  <div class="col">
    <div class="lbl">Frequencies found</div>
    <div id="spectrum" class="bars spec"></div>
  </div>
</div>
<div class="counts">
  <span class="chip naive">Naive DFT: <b id="cn">0</b> ops</span>
  <span class="chip fast">FFT: <b id="cf">0</b> ops</span>
</div>
<div class="status" id="status">Press Run FFT to decompose the signal.</div>
<div class="btns">
  <button id="run" type="button">Run FFT</button>
  <button id="shuffle" type="button" class="ghost">New signal</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Radix-2 Cooley-Tukey FFT (1965). The discrete Fourier transform pulls a signal
// apart into frequencies. Done naively it costs ~n^2 operations; the FFT splits the
// samples into evens and odds, transforms each half, and recombines them with cheap
// "butterfly" steps — so the same answer comes out in ~n*log2(n) operations.
const N = 8;
let signal = [];
let fftOps = 0;

function makeSignal(){
  // Sum of a few pure cosine waves with random amplitudes -> recognizable spectrum.
  const amps = [0,0,0,0,0]; // frequencies 0..4 (real signal -> symmetric spectrum)
  const picks = 2 + Math.floor(Math.random()*2);
  for(let p=0;p<picks;p++){ const k=1+Math.floor(Math.random()*4); amps[k]=1+Math.floor(Math.random()*3); }
  if(amps.every(a=>a===0)) amps[1]=2;
  const s=[];
  for(let n=0;n<N;n++){ let v=0; for(let k=0;k<5;k++) v+=amps[k]*Math.cos(2*Math.PI*k*n/N); s.push(v); }
  return s;
}

// Recursive FFT on complex arrays {re,im}. Counts butterfly multiply-adds in fftOps.
function fft(re, im){
  const n = re.length;
  if(n === 1) return { re:[re[0]], im:[im[0]] };
  const er=[],ei=[],or=[],oi=[];
  for(let i=0;i<n;i+=2){ er.push(re[i]); ei.push(im[i]); or.push(re[i+1]); oi.push(im[i+1]); }
  const E = fft(er,ei), O = fft(or,oi);
  const Rr=new Array(n), Ri=new Array(n);
  for(let k=0;k<n/2;k++){
    const a=-2*Math.PI*k/n; const wr=Math.cos(a), wi=Math.sin(a);
    fftOps++; // one twiddle-factor butterfly per (k, level)
    const tr=wr*O.re[k]-wi*O.im[k], ti=wr*O.im[k]+wi*O.re[k];
    Rr[k]=E.re[k]+tr;       Ri[k]=E.im[k]+ti;
    Rr[k+n/2]=E.re[k]-tr;   Ri[k+n/2]=E.im[k]-ti;
  }
  return { re:Rr, im:Ri };
}

function magnitudes(re, im){
  const m=[]; for(let k=0;k<re.length;k++) m.push(Math.hypot(re[k],im[k])); return m;
}

function renderSignal(){
  const c=document.getElementById('signal'); c.innerHTML='';
  const max=Math.max(1,...signal.map(Math.abs));
  signal.forEach(v=>{ const b=document.createElement('div'); b.className='bar';
    b.style.height=(8+Math.abs(v)/max*100)+'px'; c.appendChild(b); });
}
function renderSpectrum(mags){
  const c=document.getElementById('spectrum'); c.innerHTML='';
  const max=Math.max(1,...mags);
  mags.forEach(v=>{ const b=document.createElement('div'); b.className='bar'+(v/max>0.15?' hot':'');
    b.style.height=(2+v/max*112)+'px'; c.appendChild(b); });
}
function emptySpectrum(){
  const c=document.getElementById('spectrum'); c.innerHTML='';
  for(let k=0;k<N;k++){ const b=document.createElement('div'); b.className='bar'; b.style.height='2px'; c.appendChild(b); }
}

function run(){
  fftOps = 0;
  const out = fft(signal.slice(), new Array(N).fill(0));
  const mags = magnitudes(out.re, out.im);
  renderSpectrum(mags);
  const naive = N*N; // ~n^2 multiply-adds for the direct DFT
  document.getElementById('cn').textContent = naive;
  document.getElementById('cf').textContent = fftOps;
  // Report the dominant non-zero frequencies (bins 1..N/2).
  const hot=[]; const mx=Math.max(...mags);
  for(let k=1;k<=N/2;k++) if(mags[k]/mx>0.15) hot.push(k);
  document.getElementById('status').textContent =
    fmt('Found frequencies %hot% — FFT used %fftOps% butterflies vs %naive% naive ops.', { hot: hot.join(', '), fftOps: fftOps, naive: naive });
  console.log('FFT magnitudes:', mags.map(m=>m.toFixed(2)).join(' '), '| ops', fftOps, 'vs naive', naive);
}

function shuffle(){
  signal = makeSignal();
  renderSignal(); emptySpectrum();
  document.getElementById('cn').textContent='0';
  document.getElementById('cf').textContent='0';
  document.getElementById('status').textContent='Press Run FFT to decompose the signal.';
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('shuffle').addEventListener('click', shuffle);
shuffle();
Result
Console

Watch the two counters. The naive DFT does about n2n^{2} operations; the FFT does about nlog⁡nn \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.

The Real Complexity

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 Θ(n2)\Theta(n^2). Each of the nn output frequencies is a weighted sum over all nn inputs, so you pay n×nn \times n multiplications. This is correct and simple, but hopeless at scale.
  • The FFT is Θ(nlog⁡n)\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\log n times, doing Θ(n)\Theta(n) work per level — the textbook divide-and-conquer recurrence T(n)=2⋅T(n/2)+Θ(n)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 nlog⁡nn \log n looks like when it rescues an n2n^{2} problem that the world genuinely needs to solve, all the time.

Where It Matters

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 nlog⁡nn \log n engine under a startling amount of modern technology.

Conclusion

The Fourier transform was always a beautiful idea: every signal is a chord of pure waves. What it lacked was speed. The n2n^{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 nlog⁡nn \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 n2n^{2} and changing the world. For more on that same recursion, see fast multiplication.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fft/Content licensed under CC BY-NC 4.0.