Complexity of javascript indexOf method

Question

I studied the large O for technical interviews, and then realized that the javascript indexOf method can have O (N) time complexity when it goes through each element of the array and returns the index where it is found.

We also know that the time complexity of O (n ^ 2) (n square) is not a good measure of performance for big data.

Is it okay to use indexOf internal loops? In javascript, its common to view code, where the indexOf method indexOf used inside loops, maybe to measure equality or to prepare some object.

Instead of arrays, we should prefer objects wherever necessary, since they provide a search with constant O (1) time performance.

Any suggestions would be appreciated.

Answer 1

It is a bad idea to use the internal contours of indexOf , especially if the dataStructure you are viewing is quite large. To do this, you need to have a hash table or dictionary containing the index of each element that you can generate in O (N) by cycling through the data structure and updating it every time you add a data structure.

If you click something at the end of the data structure, O (1) Time will be required to update this table, and in the worst case, O (N) will be required to the beginning of the data structure.

In most scenarios, this will cost the index to be O (1) .

Answer 2

Honestly, tl; dr. But I did some speed tests of different ways to check for a string (if it is your goal to use indexOf. If you are actually trying to get a match position, I personally do not know how to help you there). The methods I tested are:

• .includes()
• .match()
• .indexOf()

(There are also options like .search() , .lastIndexOf() , etc. Those that I have not tested).

Here is the test:

 var test = 'test string'; console.time('match'); console.log(test.match(/string/)); console.timeEnd('match'); console.time('includes'); console.log(test.includes('string')); console.timeEnd('includes'); console.time('indexOf'); console.log(test.indexOf('string') !== 0); console.timeEnd('indexOf'); 

I know that they are not loops, but they show that they are all basically the same speed. And to be honest, everyone does different things, depending on what you need (do you want to search on RegEx? Do you need to be compatible with ECMAScript 2015? Etc. - I didn’t even list them all), is it really necessary analyze this so much?

Of my tests, indexOf() sometimes wins, sometimes one of the others wins.