does indexOf() in JS search all the elements of an array to execute?-CodePudding

const arr = ['a','b','c']; 
for (let char of arr) {
  console.log(char);
}

I believe that time complexity of code above is O(n).

const arr = ['a','b','c']; 
for (let char of arr) {
  console.log(arr.indexOf(char);
}

However, does indexOf() search all the elements? If does so, I believe time complexity of code above may be O(n^2)

I want to know whether indexOf() searches all the components as for loop or not.

CodePudding user response：

For time complexity, you always consider the worst case (for the OP's circumstance, each character is in the list at no specifically designated position). To take OP example array, doing arr.indexOf('c') would involve looking at every position until the character c is found (which is the last position). Therefore, assuming worst case scenario, the execution would take O(n) time for .indexOf(). As per @Nick Parsons comment, there are ways to improve the time of the underlying search algorithm using strategies like a binary search (which is O(log n) time complexity), but that implies the data is in some semi-structured format for any concepts like binary search to improve the time complexity.

CodePudding user response：

If the browser vendors follow the language specification, then the answer is NO. It should return once a match is found. Under certain circumstances, it will return even without checking any elements. See ECMA262.

However, complexity would be the same, O(n^2).

CodePudding user response：

Yes, the indexOf() function has a complexity of O(n). If the provided index is negative, the array is still searched from front to back. If the calculated index is less than 0, then the whole array will be searched.

So your program will have big o notation of O(n^2)

You can find more about this here at MDN