Radix 2 FFT Complexity is N Log N
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

.
Next Section: DBm ScalePrevious Section: Spectral Phase