the butterfly
Inside every FFT, the same tiny gadget fires millions of times. Drawn as a signal-flow diagram its two crossing lines look like the wings of a butterfly, which is where the name comes from. The butterfly is the atomic combining step of the algorithm: it takes two complex numbers and a weight, and produces two complex numbers.
A single radix-2 butterfly does this. Take two intermediate values a and b and a twiddle factor W^k = e^(-2*pi*i*k/N). Compute the product t = W^k * b, then output the pair a + t and a - t. That is one complex multiply and two complex additions, producing two of the transform's values simultaneously — the genuine economy is that the single multiply W^k * b is reused for both outputs (the plus version and the minus version). Stack these: a power-of-two FFT is nothing but log2(N) stages, each containing N/2 butterflies, wired so that one stage's outputs feed the next stage's inputs. Count the work and you get (N/2) * log2(N) complex multiplies — the O(N log N) cost made out of these little pieces.
Understanding the butterfly demystifies the whole FFT: the daunting transform is just an orderly army of identical add-multiply-subtract units. It also explains why FFTs are so fast on real hardware — the butterfly is a regular, predictable pattern that vectorizes well, fits in cache, and can run in place (overwriting its inputs with its outputs) so no extra memory is needed. The price of that regularity is the bit-reversal shuffle of the data order, which the algorithm has to handle either before or after the butterfly stages.
The simplest butterfly uses W^0 = 1: from a = x_0 and b = x_1 it outputs x_0 + x_1 and x_0 - x_1. That single sum-and-difference IS the entire 2-point DFT — the smallest brick from which every larger FFT is built.
One multiply, two add/subtracts, two outputs — the FFT's indivisible unit.
The butterfly is exact arithmetic on complex numbers, but its outputs reuse the inputs' memory in an in-place FFT, so the data ends up scrambled in bit-reversed order; forgetting to un-shuffle is a classic FFT bug.