What is the time complexity or Big O notation for "str.replace()" built In function in Javascript?

Question

I am confused if the time complexity for str.replace() function is O(n) or O(1), for example:

var str = "Hello World";
str = str.replace("Hello", "Hi");
console.log(str);
//===> str = "Hi World"  

Is it always the same answer or does it depend on what we replace?
Any thoughts or helpful links?!

Answer 1

Firstly it should be

str = str.replace("Hello", "Hi");

Secondly,

searching a substring inside a string can be done in linear time using KMP algorithm which is the most efficient. Replacing in the worst case will take linear time as well.

So overall time complexity: O(n)

Here n is dependent on the string str. In the worst case it will end up traversing the whole string and still not find the searchValue given to the replace function.

Answer 2

It's definitely not O(1) (comparison of string searching algorithms) , but ECMAScript 6 doesn't dictate the search algorithm:

Search string for the first occurrence of searchString and let pos be the index within string of the first code unit of the matched substring and let matched be searchString. If no occurrences of searchString were found, return string.

So it depends on the implementation.

Is it always the same answer or does it depend on what we replace?

Generally, it will be slower for longer search strings. How much slower is implementation-dependent.

Answer 3

You'll really have to look into implementation details for a complete answer. But to start there's V8's runtime-strings.cc and builtins-string-gen.cc. It's a deep dive--and I don't know c++, so I'm not entirely sure if I'm even looking at the right files, but they seem to use different approaches depending on the size of the needle and the depth of recursion needed to build a search tree.

For example, in builtins-string-gen.cc there's a block under ES6 #sec-string.prototype.replace that checks if the search_string has a length of 1, and if the subject_string length is greater than 255 (0xFF). When those conditions are true it looks like Runtime_StringReplaceOneCharWithString in runtime-strings.cc is called which in turn will try calling StringReplaceOneCharWithString first with a tree-traversable subject_string.

If that search hits the recursion limit, the runtime makes another call to StringReplaceOneCharWithString but this time with a flattened subject_string.

So, my partially educated guess here is you're always looking at some kind of linear time. Possibly O(mn) when hitting the recursion limit and doing a follow-on naive search. I don't know for sure that it's a naive search, but a flattened string to me implies traversing the subject_string step-by-step instead of through a search tree.

And possibly something less than O(mn) when the tree-traversal doesn't hit the recursion limit, though I'm not entirely sure what they're gaining by walking the subject_string recursively.

For an actual what is the time complexity for Javascript implementations, you'll probably want to ask the runtime devs directly or see if what they're doing is like other string searching algorithms to figure out which cases run in what time complexity.