More Complexity and Fork/Join

LMAX Exchange

Firstly an
apology.  On my previous blog, I mentioned that a string splitting
algorithm implemented in Scala had a complexity of O(n2)O(n^2).
 One commenter mentioned that they did not understand how I
came to that calculation.  I though I should revisit my guess work
and actually do a more thorough analysis.  What I found was
interesting, I had overstated the complexity, in reality it was O(n.log2(n))O(n.log_{2}(n)).  I’ve included my working here.

Complexity of the Scala Implementation
In the Scala implementation the list concatenation operation is O(n)O(n).
 I’ve simplified the model such that the factors applied are
different, but that shouldn’t have a bearing on the complexity.
 Fork/Join algorithms work on a divide and conquer model, in its
simplest form looks much like a binary tree.  To calculate the
complexity of the reduction part of a Fork/Join algorithm we need to sum
the the cost of all of operations to reduce the dataset to a single
result.  If we start with the base set of partial results, for the
sake of an example assume there are 8, then the first step it to reduce
them to 4.  Then second step takes the 4 partial results to create
2.  The third and final step takes the 2 results to create the
final solution. Read more

LMAX Exchange Staff Blogs Mike Barker   Foreign Exchange   LMAX Exchange  

Any opinions, news, research, analyses, prices or other information ("information") contained on this Blog, constitutes marketing communication and it has not been prepared in accordance with legal requirements designed to promote the independence of investment research. Further, the information contained within this Blog does not contain (and should not be construed as containing) investment advice or an investment recommendation, or an offer of, or solicitation for, a transaction in any financial instrument. LMAX Group has not verified the accuracy or basis-in-fact of any claim or statement made by any third parties as comments for every Blog entry.

LMAX Group will not accept liability for any loss or damage, including without limitation to, any loss of profit, which may arise directly or indirectly from use of or reliance on such information. No representation or warranty is given as to the accuracy or completeness of the above information. While the produced information was obtained from sources deemed to be reliable, LMAX Group does not provide any guarantees about the reliability of such sources. Consequently any person acting on it does so entirely at his or her own risk. It is not a place to slander, use unacceptable language or to promote LMAX Group or any other FX and CFD provider and any such postings, excessive or unjust comments and attacks will not be allowed and will be removed from the site immediately.