Is it a bad idea to use indexOf inside loops?

Question

I was studying big O notation for a technical interview and then I realized that javascript's indexOf method may have a time complexity of O(N) as it traverses through each element of an array and returns the index where its found.

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

So is it a bad idea to use indexOf inside loops? In javascript, its common to see code where indexOf method is being used inside loops, may be to measure equality or to prepare some object.

Rather than arrays, should we prefer objects wherever necessary as they provide lookup with constant time performance O(1).

Any suggestions will be appreciated.

Answer 1

It can be a bad idea to use indexOf inside loops especially if the dataStructure you are searching through is quite large. One work around for this is to have a hash table or dictionary containing the index of every item which you can generate in O(N) time by looping through the data structure and updating it every time you add to the data structure.

If you push something on the end of the data structure it will take O(1) Time to update this table and the worst case scenario is if you push something to the beginning of the data structure it will take O(N).

In most scenarios it will be worth it as getting the index will be O(1) Time.