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.