Big O of javascript built-in split function

Question

Example:

var string = "abcde";
var array = string.split("");
// array = ["a", "b", "c", "d", "e"]

What is the amortized running time of this split function? Also, how do I view source code of such built-in functions in javascript?

Unless the browser is open-source, you can't view the source code. — Barmar, Nov 02 '15 at 17:53
Probably something about `O(n*k)` (with `n` the length of the splitted string and `k` some factor that depends somehow on the argument, such as the length or type of the delimiter and the number of results) — Bergi, Nov 02 '15 at 17:54
I dont think this question has a single answer. While `string.split` is defined in the [spec](http://www.ecma-international.org/ecma-262/5.1/#sec-15.5.4.14), the specific algorithm used can vary by vendor. However, the spec does spell out the general structure of the algorithm. Perhaps it's possible to estimate `O(string.split)` based on the spec. — , Nov 02 '15 at 18:03
@Amy While anything is conceivable, this is such a simple operation that there aren't really many realistic choices of implementation. — Barmar, Nov 02 '15 at 18:04

score 6 · Answer 1 · answered Nov 02 '15 at 18:01

6

With an empty delimiter argument, split is essentially equivalent to:

var len = string.length;
var result = Array(len)
for (i = 0; i < len; i++) {
    result[i] = string[i];
}

This is O(len).

With a delimiter, it becomes O(string.length * delimiter.length), because at each step in the loop it has to test whether there's a match for delimiter.

answered Nov 02 '15 at 18:01

Barmar

669,327
51
454
560

1

Is there any documentation, proof or test you can cite for this statement? – zardilior Nov 16 '20 at 03:50
Not that I know of, but there's practically no other reasonable way to implement it – Barmar Nov 16 '20 at 06:13
What language allows finding all the delimiters in a string without searching for them with nested loops? Even if there's a hardware operation to do the string comparison, that's still a loop in the CPU. – Barmar Nov 17 '20 at 16:03
To me, this is `O(n)`. – ncardez Jun 22 '21 at 17:41
Yes, `n == len` – Barmar Jun 22 '21 at 18:20

score 0 · Answer 2 · answered Apr 16 '20 at 09:39

It's not very straightforward. The complexity will depend on the delimiter(whether it is a string or a regex). For every iteration, the string is searched for a match on the delimiter. The big O will essentially be O(len * big O of search algorithm) where len is the number of substrings.

score -4 · Answer 3 · edited May 23 '17 at 10:27

-4

EDIT: The OP did ask "What is the amortized running time of this split function?". This is an answer to this precise question

To get the real running time of a function, see : How to measure time taken by a function to execute

var start = new Date().getTime();

for (i = 0; i < 50000; ++i) {
// do something
}

var end = new Date().getTime();
var time = end - start;
alert('Execution time: ' + time);

You can't view JS source code, as it's built-in each navigator. You can take a look at Chromium project, maybe you'll find what you are looking for.

I don't know how to get the amortized time of the split, and I dont think you can calculate it without having access to source code.

edited May 23 '17 at 10:27

Community

1
1

answered Nov 02 '15 at 17:53

Raphaël Vigée

2,008
13
26

3

Running time is **not** the same thing as Big O. – Nov 02 '15 at 17:54
3

To be fair the OP did ask: *"What is running time of this split function?"*. But yes running time doesn't say anything about the Big-O. But this does technically answer the question asked in the body @Amy. – Spencer Wieczorek Nov 02 '15 at 17:54

Big O of javascript built-in split function

3 Answers3

Linked