Consider you have been given an array of N21 9 data points e

Consider you have been given an array of N=2^1 9 data points (e.g. from a data logger). You now want the computer to calculate a Fourier series using a Discrete Fourier Transform (DFT) algorithm Therefore each complex Fourier coefficient is calculated using the following formula C_n = Sigma^N-1_K=0 F_Ke^-i2 pi k n/N n =0, 1, 2..., N-1 The calculation of each of those individual summands F_K^e^-12 pi k n/N takes lns=10^-9 S. How long will the computer need to calculate all Fourier coefficients? In order to reduce the computing time the number of data points used as input to the Fourier analysis is reduce by 50%. What percentage of time (compared to part a)) can you save using the same algorithm?

Solution

A) Time complexity to calculate DFT Algorithm i.e. FFT Algorithm is :- O(NlogN)

   N=2^19

Time Complexity T(N)= O(19*2^19log2)=19*2^19*0.303=2988441.6 ns = 2.9ms.

B) Time Complexity =1415577.6 ns=1.4 ms

% of time of algorithm = (1.4/2.9)*100= 48.2%

Therefore 48.2% of time we can save using FFT Algorithm