MATLAB: How to properly measure computational complexity (run-time) in Matlab

Question

Basically, I am implementing an algorithm that has the same computational complexity as the FFT function in Matlab? The complexity is O(n log n). The algorithm I am implementing also has the same complexity. I am using wavelet transforms to compute FFT which produces the exact same results as the regular FFT function.

However, when I use tic and toc to measure the speeds, my algorithm takes longer than the classic FFT approach. It's spending a lot of time in the wavelet transform function that I'm using from the Wavelet toolbox.

Any suggestions? How do I really measure/judge computational complexity?

Answer 1

In order to get an experimental feel for computational complexity, you need to run the code with several different sizes of problems, and model how the time increases as the size of the problem increases.

Keep in mind that computational complexity is insensitive to constant multipliers or constant additions. Something that takes (say) always 100000 times longer, would be considered the same complexity.