Calcul du nombre d'opérations à effectuer

A la dernière étape du calcul on dispose du résultat de deux transformées de Fourier de taille $N=T/2$. Pour en déduire la transformée de taille $T$ il faut effectuer $T/2$ multiplications, $T/2$ additions et $T/2$ soustractions. A l'étape précédente, on dispose de quatre transformées de Fourier de taille $T/4$ et on en déduit deux transformées de taille $T/2$. Pour chacune d'elles il faut effectuer $T/4$ multiplications soit au total $T/2$ multiplications. On voit ainsi que pour chacune des étapes ( où la tailles de vecteurs est $T, T/2, \cdots,T/2^m,\cdots,4,2,1$ et où le nombre de vecteurs est $1,2,4,\cdots, T/2^m, \cdots,T/2,T$), il est nécessaire d'effectuer $2^{m-1}\times\frac{T}{2^m}$ multiplications. Il y a au total $\log_2 T$ étapes et il faut donc effectuer $\frac{T}{2}\log_2(T)$ multiplications.