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

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

[Walter Roberson]

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.

[John]

If I run one algorithm that grows O(N) with the different sizes and then I run another algorithm that grows O(N^2), the O(N) algorithm is better? However, what if O(N) takes longer to run than O(N^2)? If I understand you correctly, the O(N) is still better in terms of complexity?

[Walter Roberson]

Complexity represents the limit of efficiency as the problem size gets larger. So your O(N) code might take 10000*N and so might be much slower for small values than O(N^2) code that takes 3/2 * N^2 (for example), but past N=15000 or so the 10000*N would be faster than the 3/2 * N^2.