I am implementing an algorithm that has been proven to be O(log N). I implemented it using some of the built-in functions in Matlab as well as manually without these functions.They are taking longer than O(log N) for increasing values of N. It's closer to O(N^2) which is not acceptable.What's going on? I am trying to improve the performance of this algorithm but need to baseline it at O(log N).

Which algorithms in particular? QuoteInformally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function f(n) times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n0 and a constant c, the running time of that algorithm will never be larger than c × f(n). This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order O(n²).Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case ? for example, the worst-case scenario for quicksort is O(n²), but the average-case run-time is O(n log n).[7]

A binary search algorithm. Something is going on with Matlab.

Function calls in MATLAB have a large overhead, so your implementation MUST be iterative and not recursive. One possibility is:1) Iteratively subdivide your data (just like the binary search)2) Stop the data subdivision when a block of data suitably sized. i.e. small enough the O(N) does not hurt very much but large enough to take advantage of MATLAB's vectorized processing3) Use the find function on the data blocks to search for your valueIf all else fails, MATLAB's find function will do the same thing as a binary search but with O(N) complexity. The advantages are find is optimized compiled code and it well take advantage of the vectorization capabilities of MATLAB.

How big is N? For large N, I would think that memory management issues come into play.

can you post the code?

Of course, performance is not the first word that springs to mind when I think of Matlab. I vaguely remember that function calls are awful expensive.

I eliminated recursive function calls and just used for loops. It's faster but not as fast as I would like but better than before.

I am such a retard. I was comparing my own Matlab implementation with built-in Matlab functions/algorithms. Of course, Matlab's built in functions would be faster since they are compiled source code.I'll have to implement the equivalent of those Matlab built in functions which should serve as a fair comparison.