MATLAB: How to find the cost for implementing an fft

Question

I wantto find the cost involved in implementing an fft that is the number of multiplications and additions as i have a task to compare it with normal DFT function to see the difference between the cost in implementing both the functions.

Answer 1

I guess you mean the cost involved in executing an fft. (The cost involved in implementing an fft would the amount you'd need to pay your team to write the code, I suppose.)

I guess by "normal DFT function" you mean the naive implementation, based on the DFT formula in textbooks. (Arguably, the FFT is the normal implementation, as some version of the FFT is always used in practice.)

Nit-picking aside, there are two things you could do:

1. Write a naive DFT function using the formula you'll find in any textbook, Wikipedia etc. Time it on some random data using cputime or tic and toc, and compare that time with the time taken using the fft function. If you do it properly (plenty of data, repeat the computation a number of times and take the fastest) then you will get a time roughly proportional to the number of multiplications and additions that have been executed. (Check your naive DFT function and fft give the same numerical results, to within a small tolerance.)
2. Analyse the two methods and work out how many multiplications and additions take place for each. You don't need to write any code for this - you just have to understand the algorithms. If you look up "computational complexity" you'll find textbooks and web pages that will help you greatly with this analysis. You'll find it easiest if you stick to the simplest kind of FFT which assumes that the data length is a power of 2.