Complexité de la fft ?

[Poliamel72]

Bonjour,
Je suis actuellement en train de rédiger mon mémoire sur l'implémentation de la FFT, et je galère a raisonner sur la réduction de la complexité.

On part du principe que la DFT est complexité N*N (nombre de multiplication complexe avec N longueur de la FFT).
Pour un étage de division (en temps ou en fréquence) , la comp devient (N*N)/2 + N/2
Pour deux etages, la comp devient (N*N)/4 + N
Pour log2(N) étages, la comp est censé devenir log(N)*(N/2).

Or, je ne comprends pas ce dernier passage. Quelqu'un pourrait m'éclairer ?