Please also explain the algorithm, include proof of correctness (loop invariants, etc), and the time complexy.

(15 points) For any positive integer k, let [k] denote {0,,k1}. On the last slide of the FFT lecture, we defined the discrete Fourier transform (DFT) of a given vector a=(a0,,aN1) (of complex values) as the vector (A(N0),,A(NN1)) where A(x)=0k