Fourier Transform, Fft, Fast Fourier Transform, Algorithms, Mathematics.
symmetrical along the frequency axis. It is enough to take only the 1st half values. The time complexity for calculating the DFT with input size of n is O(n²) because for each frequency v, we are calculating the sum with n terms of the input f(t) and there are n different values of v from 0 to n-1