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 .