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?!

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?!

• javascript
• string
• big-o

• 3 Are you sure that the return value of str.replace("Hi")? – ibrahim mahrir Commented Nov 9, 2017 at 18:48
• the definition is string.replace(searchvalue, newvalue) – Francesco Taioli Commented Nov 9, 2017 at 18:49
• sorry I've just edited it@ibrahimmahrir – Zainab Hammami Commented Nov 9, 2017 at 18:50
• Possible duplicate of How to find time complexity of an algorithm – devlin carnate Commented Nov 9, 2017 at 18:51
• I think it's implementation-dependent. It could be different for V8, Rhino, and Nashorn. – David Ehrmann Commented Nov 9, 2017 at 18:51

3 Answers 3

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.

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.

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.