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?

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?

• javascript
• big-o

• 6 Unless the browser is open-source, you can't view the source code. – Barmar Commented Nov 2, 2015 at 17:53
• 3 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 Commented Nov 2, 2015 at 17:54
• 3 @Bergi Multiplying by a constant doesn't change big O. – Barmar Commented Nov 2, 2015 at 17:55
• 3 @Barmar: I didn't mean that k is a constant. – Bergi Commented Nov 2, 2015 at 17:56
• 1 @Amy While anything is conceivable, this is such a simple operation that there aren't really many realistic choices of implementation. – Barmar Commented Nov 2, 2015 at 18:04

3 Answers 3

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 bees O(string.length * delimiter.length), because at each step in the loop it has to test whether there's a match for delimiter.

It's not very straightforward. The plexity 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.

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.