Fast Fourier Transform — Radix-2 Cooley-Tukey

The DFT splits coefficients by even/odd index and recombines with the butterfly âk = Ek + ωkOk, âk+n/2 = Ek − ωkOk. Watch the O(n log n) divide-and-conquer build the transform.

step 0

Divide & conquer tree (even / odd split & butterfly combine)

even-index group odd-index group active butterfly

Roots of unity (n = 8)

Press Step to begin.
We compute the DFT by recursively splitting the coefficient array into its even-indexed and odd-indexed halves, transforming each, then combining with butterflies that reuse the halving property (ωnk)² = ωn/2k.
Self-contained visualization. Forward DFT over the complex roots of unity ωn = e2πi/n. Recurrence T(n) = 2T(n/2) + O(n) = O(n log n). The bottom row shows bit-reversed leaves; each stage applies one butterfly pass. See junior.md and professional.md for the proof that âk = Ek + ωkOk.