X[k] = Σn=0N−1 x[n] · WNnk
where
WN = e−i2π/N (twiddle factor)
For each output bin k: sum over all N input samples × a rotating complex exponential
N (samples):8Output bin k:
Twiddle factor WNnk — unit circle
Input x[n] × twiddle (real-part contribution)
Full DFT magnitude — |X[k]| for all k
For each output bin k, you multiply all N input samples by a spinning complex exponential and sum them up. That is why the direct DFT costs N² multiplications. When the twiddle factor lines up with a frequency in the input, the contributions add up constructively.