Putting together the length DFT from the length- DFTs in
a radix-2 FFT, the only multiplies needed are those used to combine
two small DFTs to make a DFT twice as long, as in Eq. (A.1).
Since there are approximately (complex) multiplies needed for each
stage of the DIT decomposition, and only stages of DIT (where
denotes the log-base-2 of ), we
see that the total number of multiplies for a length DFT is
reduced from
to
, where
means
``on the order of ''.

More precisely, a complexity of
means that given any
implementation of a length- radix-2 FFT, there exist a constant
and integer such that the computational complexity
satisfies

for all . In summary, the complexity of the radix-2 FFT is said
to be ``N log N'', or
.