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 $N\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 radix-2 FFT, there exist constants $C_1$, $C_2$, and $C_3$ such that the computational complexity ${\cal C}(N)$ as a function of the FFT size $N$ satisfies

$${\cal C}(N) \leq C_1 N \lg N + C_2 N + C_3.$$

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