Radix 2 FFT Complexity is N Log N

Putting together the length $N$ DFT from the $N/2$ length-$2$ 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 $N$ (complex) multiplies needed for each stage of the DIT decomposition, and only $\lg N$ stages of DIT (where $\lg N$ denotes the log-base-2 of $N$ ), we see that the total number of multiplies for a length $N$ DFT is reduced from ${\cal O}(N^2)$ to ${\cal O}(N\lg N)$ , where ${\cal O}(x)$ means ``on the order of $x$ ''. More precisely, a complexity of ${\cal O}(N\lg N)$ means that given any implementation of a length-$N$ radix-2 FFT, there exist a constant $C$ and integer $M$ such that the computational complexity ${\cal C}(N)$ satisfies

$${\cal C}(N) \leq C N \lg N$$

for all $N>M$ . In summary, the complexity of the radix-2 FFT is said to be ``N log N'', or ${\cal O}(N\lg N)$ .