In the case of the radix-2 Cooley–Tukey algorithm, the butterfly is simply a DFT of size-2 that takes two inputs (
x0,
x1) (corresponding outputs of the two sub-transforms) and gives two outputs (
y0,
y1) by the formula (not including
twiddle factors): :y_0 = x_0 + x_1 \, :y_1 = x_0 - x_1. \, If one draws the data-flow diagram for this pair of operations, the (
x0,
x1) to (
y0,
y1) lines cross and resemble the wings of a
butterfly, hence the name (see also the illustration at right). More specifically, a radix-2 decimation-in-time FFT algorithm on
n = 2
p inputs with respect to a primitive
n-th root of unity \omega^k_n = e^{-\frac{2\pi i k}{n}} relies on O(
n log2
n) butterflies of the form: :y_0 = x_0 + x_1 \omega^k_n \, :y_1 = x_0 - x_1 \omega^k_n, \, where
k is an
integer depending on the part of the transform being computed. Whereas the corresponding inverse transform can mathematically be performed by replacing
ω with
ω−1 (and possibly multiplying by an overall scale factor, depending on the normalization convention), one may also directly invert the butterflies: :x_0 = \frac{1}{2} (y_0 + y_1) \, :x_1 = \frac{\omega^{-k}_n}{2} (y_0 - y_1), \, corresponding to a decimation-in-frequency FFT algorithm. ==Other uses==