What is the algorithm complexity (Big(O)) of built-in JS methods?

Question

JavaScript

Hey!
I began to study in more detail the estimation of the complexity of algorithms. And several questions arose:
1) Can the same methods in different languages ​​have different complexity?
2) Where can I find official information on the complexity of built-in methods in Javascript?
I have looked at various forums and articles, and sometimes one method is assigned one difficulty, in another place - another.
Now I'm watching a course on complexity estimation and there, for example, string concatenation is estimated at O ​​(N ^ 2)



In JS, string concatenation is estimated at the same complexity?
I would be very grateful if you tell me where to look for reliable information on this topic within the framework of JS.

Answer 1

1. Complexity depends on the algorithm used in a particular implementation. Therefore, in V8, the complexity may not be the same as in the Firefox JS engine.
2. View source code. Especially since it's open.
Adding to a string one letter at a time is repeating the string concatenation N times. Therefore complexity also turns out O(N**2). This example has nothing to do with estimating the computational complexity of concatenation.
In the real world, the complexity of concatenating strings of length N and M, even in the worst case, does not exceed O(N + M).

Answer 2

It looks like the documentation does not indicate the complexity of the methods. Apparently, no one expects performance from js code =)
Here the situation is further complicated by the fact that the standard does not contain requirements for complexity. Therefore, the same functions in different browsers, theoretically, can have different complexity.
Perhaps you can google something on specific methods.
According to the description of the concat method, it returns a new string without changing the arguments. Therefore, most likely, it works for the linear complexity of the total length of the operands. It is unlikely that rope is used there .

Answer 3

The representation of strings in different JS engines is different.
In V8, a string can be represented as an array or as a tree. When concatenating strings, a tree is just used. There's even a flatstr project that converts the tree representation to a flat one so that other string operations can be done faster.