I'm trying to analyze the complexity of MATLAB code I wrote.I'm trying to figure out how much (in terms of $O$ or $\Theta$) to give functions like find, matrix * operator, matrix .* operator, and others.Is there a way to calculate this? Or a reference?
What is the Complexity of MATLAB operations
matlab;complexity
Matlab 6 used to have a function flop to count them, but it was removed in later versions. The main reason was technical (they switched to LAPACK as the linear algebra core, and it did not return a flop count). Today this option isn't available anymore; there is no easy equivalent, so if you wish to have one you'll have to count them yourself using the definition and your best guess on how these operations are implemented. It should be easy to come up with big-O estimates; not always so to pin down the exact constant. In the examples you ask for it is easy to guess what Matlab is doing and counting the operations by hand, but it isn't always so.In some cases, such as the QR/Francis algorithm for computing eigenvalues (eig), this constant will depend on the specific matrix. Appendix C of Higham's Function of Matrices contains good reference values for some dense linear algebra operations. However, the real answer depends on the details of Matlab and LAPACK implementation, which is ultimately unknown since the former is closed source, and it will often change from version to version.In addition, let me point out that the answer depends on how you define $O$ / $\Theta$ complexity. A common choice in most theoretical papers is arithmetic operations such as sums and products count 1, everything else is free (sometimes called flop count). With this definition, however, find costs zero, since it makes a bunch of comparisons but no true arithmetic operation. To play devil's advocate, you can even replace a floating point operation with a bunch of comparisons and assignments. So there are plenty of reasons to think that it is not a good choice.For a less contrived example, consider Gaussian elimination with complete pivoting: it has the same flop-count cost as partial pivoting, but it involves $O(n^3)$ comparisons rather than $O(n^2)$, and these comparisons increase its actual cost.Moreover, the execution time on a modern computer does not depend (only) on flops anymore. Details such as memory layout, cache misses, branch prediction have a large impact. There is no easy way to tell how long an operation will take, apart from running it and measuring the time. Check out this thread for an illuminating example. There is a whole research area on how to reduce  hidden costs such as memory access in linear algebra operations; check for instance the section communication-avoiding algorithms on Jim Demmel's home page.The performance of Matlab itself is another can of worms. Matlab is an interpreted language, and it does lots of additional work and bookkeeping between the lines. If you use Matlab profiler to check which instructions take the most time, you'll often find that the culprits are surprisingly unusual lines such as memory allocations, comparisons, or calls to functions which do almost nothing. Merely putting a function in a namespace or a class can have a huge impact on its execution time.A JIT compiler (Matlab accelerator) optimizes some tight cycles, but since it is itself closed-source and continuously evolving, it's impossible to predict if and when it will kick in. The Mathworks explicitly refuse to provide an interface to tell if a function has been JIT-compiled or not. 