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