SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

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

March 7th, 2013, 3:07 pm

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

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

March 7th, 2013, 3:09 pm

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

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

March 7th, 2013, 3:56 pm

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

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

March 7th, 2013, 4:09 pm

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

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

March 7th, 2013, 4:13 pm

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

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

March 7th, 2013, 4:34 pm

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

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

March 7th, 2013, 9:01 pm

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

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

March 8th, 2013, 1:32 am

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

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

March 9th, 2013, 12:42 am

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.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On