How to compare the complexity of two algirthms in MATLAB

I have to Algortihms for my simulations. Both are working but I need to compare the complexity/effiency of the two algorithm...something like a Big O notation

Answer 1

[Torsten]

Count the number of arithmetic operations used by both depending on the input.

E.g. usual matrix multiplication needs m*n*o multiplications and additions where the first matrix is (mxn) and the second is (nxo).

[Cutie]

Thank you for your response but is this the same as Big O notation?

Is there a Big O notation for SVD operation?

[Torsten]

Thank you for your response but is this the same as Big O notation?

Yes, m*n*o is O(m*n*o) with the constant 1.

Is there a Big O notation for SVD operation?

See

https://stackoverflow.com/questions/29218823/time-complexity-of-singular-value-decomposition

[Cutie]

Thank you @Torsten

Answer 2

[John D'Errico]

Sorry, but this has been discussed many times before on this site. There is no tool that does it for you, nor can one easily be written.

If you absolutely need that information, then you will need to spend the time and do the work yourself, based on known behaviors for SOME of the computations you are doing. For example, things like a matrix multiply, etc., have known complexity. But there is a problem, even with that.

Computers today have many other factors that enter into the problem, like having multiple cores, so SOME of the time, MATLAB is able to speed up computations greatly using all of the ocres on your computer. (Would you really want that to not be able to happen? Are you kidding? People would be incensed if MATLAB did not work as rapidly as possible.) As such, your somputer has multiple cores, that can SOMETIMES be fired up, but running other code on multiple cores would just slow things down. (Symbolic computations are a good example there, where only one core will run, but linear algebra is accomplished using the BLAS, which will happily use all of your available cores.)

And every computer may have different amounts of RAM, of CACHE memory, etc. So how your computer runs any specific piece of code need not be the same as how mine will. Different computers, with 2 or 4 or 8 or 16 cores, will all see very different behaviors. As such, a direct flops count as you ask for is virtually meaningless.

But feel free to do the work yourself, if you can However, there is no automatic tool that can do it for you.

At best, perhaps you can invest the time to run your code, with different problem sizes, retaining the overall time required to run. (Remember that tic and toc are not good estimators of actual time spent. This is why MATLAB provides tools like timeit, which do a FAR better job of time estimation. But even timeit can be problematic, as you do NOT want to be surfing the web while MATLAB is doing such a time test. That would completely invalidate any such test.)

Having now devaloped such a time profile, as a function of problems size, you could now model time versus problem size, and devalop your OWN O(N) model. It would be valid ONLY for your computer, of course. And ONLY valid as long as that computer is doing nothing else on the side. (Be careful even there, as my computer is set to automatically do things like back up once a day. It uses antivirus tools to scan the disk periodically. It does lots of stuff in the background, all of which will invalidate any flops count estimate.)

[Cutie]

Thanks @John D'Errico for this detailed explanation.