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

3 次查看（过去 30 天）

Raushan 2022-9-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1810430-how-to-show-that-dft-follows-n-2-number-of-operations

评论： Chunru 2022-9-23

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Chunru 2022-9-23

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1810430-how-to-show-that-dft-follows-n-2-number-of-operations#answer_1059060

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.