 blackscholes
Topic Author
Posts: 87
Joined: February 16th, 2012, 12:58 pm

### Big O (Computational Complexity) in Matlab - What's going on?

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). Cuchulainn
Posts: 63232
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Big O (Computational Complexity) in Matlab - What's going on?

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).
Last edited by Cuchulainn on March 6th, 2013, 11:00 pm, edited 1 time in total.
Step over the gap, not into it. Watch the space between platform and train.
http://www.datasimfinancial.com
http://www.datasim.nl blackscholes
Topic Author
Posts: 87
Joined: February 16th, 2012, 12:58 pm

### Big O (Computational Complexity) in Matlab - What's going on?

A binary search algorithm. Something is going on with Matlab. OOglesby
Posts: 42
Joined: August 26th, 2011, 5:34 am

### Big O (Computational Complexity) in Matlab - What's going on?

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. Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Big O (Computational Complexity) in Matlab - What's going on?

How big is N? For large N, I would think that memory management issues come into play. isometry
Posts: 38
Joined: April 14th, 2012, 2:53 pm

### Big O (Computational Complexity) in Matlab - What's going on?

can you post the code? Cuchulainn
Posts: 63232
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Big O (Computational Complexity) in Matlab - What's going on?

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.
Last edited by Cuchulainn on March 6th, 2013, 11:00 pm, edited 1 time in total.
Step over the gap, not into it. Watch the space between platform and train.
http://www.datasimfinancial.com
http://www.datasim.nl blackscholes
Topic Author
Posts: 87
Joined: February 16th, 2012, 12:58 pm

### Big O (Computational Complexity) in Matlab - What's going on?

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. blackscholes
Topic Author
Posts: 87
Joined: February 16th, 2012, 12:58 pm

### Big O (Computational Complexity) in Matlab - What's going on?

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.  