The DFT computes each frequency bin by accumulating every input sample times a rotating phasor

The Discrete Fourier Transform turns N real time-domain samples into N complex frequency-domain values. The book’s pseudocode makes the algorithm explicit: an outer loop over frequency bins k and an inner loop over sample indices n, accumulating X[k] += Complex(x[n]) * Exp(E, -i2Pi/N * n * k). Each bin is thus the sum of all input samples, each rotated by a phasor whose angle advances with both the bin frequency k and the sample position n. The two nested loops make it an O(N^2) computation. Constants (the imaginary unit I, Euler’s e, and -i2Pi/N) are set up once before the loops.

Examples

ComplexList DFT( RealList x ): N = Length(x); for k in 0..N-1 { X[k] = 0; for n in 0..N-1 { X[k] = X[k] + Complex(x[n],0) * Exp(E, mI2pidN * n * k) } }.

Assessment

Given the double-loop DFT pseudocode, state the time complexity and explain what the inner-loop term Exp(E, mI2pidNnk) represents geometrically (a phasor rotation).