A la dernière étape du calcul on dispose du résultat de deux
transformées de Fourier de taille 
. Pour en déduire la
transformée de taille 
il faut effectuer 
multiplications,
additions et soustractions.
A l'étape précédente, on dispose de quatre transformées de Fourier
de taille 
et on en déduit deux transformées de taille .
Pour chacune d'elles il faut effectuer multiplications soit
au total multiplications. On voit ainsi que pour chacune des
étapes ( où la tailles de vecteurs est
et où le nombre
de vecteurs est
),
il est nécessaire d'effectuer
multiplications. Il y a au total 
étapes et il faut donc
effectuer
multiplications.
[ Table des matières ]