How to show that DFT follows N^2 number of operations?

Hey!

Let's say I have a matrix with 4096 data in one column.FIrst, I took 256 data from that to perfom DFT(without FFT) and FFT both and record the time needed for each operation. Then I took 1 to 512 data and do the same. Similarly I took 1 to 1024 data to perform the same operation and kept going like this till 4096.

It is known that number of operations for FFT follows N logN trend (where N is the sample size) and DFT follows N^2 trend. I am trying to plot for time required for each operation vs number of sample and somehow show that they follow the trends as mentioned. I am not understanding if I should do a polyfit or just loglog plot for both axes and see the curve is linear for both cases or not. What should I do in this case?

Any help will be appreciated.

Answer 1

[Chunru]

One simple way is to plot sqrt(dft_time) vs n to see if it is a straight line.

Generally speaking, the computation time can be a very complicated thing. The DFT/FFT computations not only depending on the number of mulitplication/addtions (N^2 and N*log2(N)), but also depend on how the coefficients are computed and how memory are accessed (espcially with cache memory structure) and how index are generated, never mentioning the overhead of fft implementation in matlab.

[Raushan]

Thanks for the information. I figured out N^2 trend for dft it is coming out linear, but I am not able to do the fit N*Log(N)trend for fft. It is also supposed to come out linear.

[Chunru]

n = 2.^(6:20);
t = zeros(size(n));

for i=1:length(n)
    x = randn(n(i), 1);
    tic; fft(x); t(i)=toc;
end
figure; plot(n, t, '-*')

figure
plot(n.*log2(n), t, '-*')
mdl = fitlm(n.*log2(n), t);
hold on
plot(n.*log2(n), feval(mdl, n.*log2(n)) )

[Raushan]

That’s great but seems like you fit the trend in x axis.

I am also doing similar but my plot is not coming linear. I am using the following data

Fft time = [0.0007077, 0.000745, 0.000908, 0.001134, 0.003320]

X = [256, 512, 1024, 2048, 4096]

Then I am trying to fit N*Log(N) in fft time but I am not getting linear plot.

[Raushan]

For N^2 I used P= polyfit(x, dft_time,2) Plot(x, p(1).*x^2)

And I got linear trend. I am trying similar for fft to fit N*Log(N) but not getting linear.

Do I need to use some other fit for this?

[Chunru]

See the update for fitting.