Time complexity of string split map combination

Question

I am wondering how to calculate time complexity of such combination:

"some string"
   .split(" ") // O(n)
   .map( 
      word => doSomething(word) // word length = j, doSomething(word) => O(j)
    ) // O(n * j) => O(n^2) ???

doSomething is a linear complexity function, doesn't metter what its doing.

So, according to Big O of javascript built-in split function , time complexity of .split(" ") will be O(n)

On next line we have a .map on words array, which in worst case can be O(n/2) => O(n) when we have all words containing one char.

Inside map function we do some operation on the word with length j => O(j). Taking into account, that word can be size of full string (no spaces) O(j) => O(n)

As result we have overal time complexity O(n^2)

BUT if we have worst case on .map step O(n) then we can't have worst case inside map, becase overall sum of all words length is size of input string. So we can't convert O(j) to O(n)

What will be time complexity then ?

Update

Ok, i made some experimental measures and here what i've got on my pc https://www.wolframalpha.com/input/?i=listplot%5B%7B%7B10%2C+0.015%7D%2C%7B100%2C+0.1%7D%2C%7B1000%2C+0.72%7D%2C%7B10000%2C+8.5%7D%2C%7B100000%2C+67.89%7D%2C+%7B1000000%2C+642.60%7D%2C+%7B10000000%2C+6657.4%7D%2C+%7B100000000%2C+70076.01%7D+%7D%5D

X axis => time ms

Y axis => input string length

data generated randomly

The complexity is clearly linear.

you are chaining operations. It's not multiplicative, but sequential. — ASDFGerte, Oct 21 '19 at 17:56
@ASDFGerte, yes, but in worst case split can give us n/2 results, so next .map complexity will be O(n) ? — Vololodymyr, Oct 21 '19 at 17:57
When chaining O(n) operations, the entire thing is still O(n). You are first doing n operations, then again n, that's still O(n). There is a lot of math and calculation rules about O-notation, but the important thing here is that it's still linear time complexity, and therefore no issue at all. — ASDFGerte, Oct 21 '19 at 17:58
@ASDFGerte, So doesn't metter what we do in `map` function its still O(n) ? — Vololodymyr, Oct 21 '19 at 18:00
Of course, you can always do something complex in `map`, but that's not your example. Your example is something that goes over words in O(wordlength), and you do that for every word, that's O(n). (wordlength * words = characters = n) — ASDFGerte, Oct 21 '19 at 18:01
sorry, still confused :S , we doing `doSomething(word)` N times, doSomething itself is O(word.length), so in result we should have O (N * word.length). Can we assume here that `N * word.length` == n — Vololodymyr, Oct 21 '19 at 18:05
@ASDFGerte that is true for the operations on the array itself, but the processing in `doSomething(...)` is ran for each element. So, the complexity of that function will be multiplied by the number of iterations of `map`. The complexity should be `O(n)` since the `doSomething(...)` as described is related to the length of the split string. At most it will do something on string of length `n` a single time or it will process a single character `n/2` times. Regardless, the processing is completely a linear function based on the length of the string, so `O(n)`. — Daniel W Strimpel, Oct 21 '19 at 18:05
@DanielWStrimpel as per his example, `doSomething` is O(j), where j is the wordlength. You do that for every word, that's n again. You do one O(n) operation, `split`, then another O(n) operation, `map` (with `doSomething`), resulting in a total of O(n). The main thing i want to emphasize is actually, that first doing `split`, then doing `map`, is not multiplicative between another. You chain two O(n) operations, that won't get you to O(n^2), which is however what he suggests in his question. — ASDFGerte, Oct 21 '19 at 18:08
I think the confusion comes from me not fully understanding, where OP's problem lies. In your argumentation, you are doing a "complexity is cleary less or equal than", the "which in worst case can be O(n/2) => O(n)" **together with** "word can be size of full string". That is possible, and you conclude it will be at most O(n²). However, that is not useful. As the sum of characters for each word is equal to the strings characterlength, the complexity will be lower than your chosen upper limit. — ASDFGerte, Oct 21 '19 at 18:31
To elaborate further, you are assuming worst case on two points, while those two cannot happen at the same time. If one word is the size of the whole string, you cannot have more than one word, and on the other hand, if you have one character per word, you have exactly that, one character per word. The sum will always be the same, the total length of the original string. — ASDFGerte, Oct 21 '19 at 18:37
Nice :). Sorry for the initial confusion. I think it stemmed from me not slowly and rigorously reading the question, and as a result not clearly understanding, which part you were having an issue of understanding. — ASDFGerte, Oct 21 '19 at 18:43

score 0 · Accepted Answer · answered Oct 21 '19 at 21:18

The code is O(n), where n is the length of the string:

I would agree with split being O(n).

The interesting part is the map. Here, you give correct arguments for an upper limit in complexity. It is true, that the code is also O(n²) (note, that O(n) is a subset of O(n²), trivially, so there is no contradiction). However, a more precise evaluation can be done. Notice, that the worst cases for your estimate cannot both occur at the same time:

If one word is the size of the whole string, you cannot have more than one word
If you have one character per word (maximum amount of words), you have exactly that, one character per word

The sum of characters of every word will always be the length of the sentance. The complexity is O(sum of all words' character lengths), and instead of estimating both character length and amount of words at the worst case, we notice this is simply O(n).

As sequential chaining of a constant amount of O(n) operations is still O(n), we get the above mentioned overall complexity of O(n), where n is the amount of characters.

Time complexity of string split map combination

1 Answers1