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