CODEWITHSUNDEEP
javascriptalgorithmperformancebig-oindexof
Vatsal
Vatsal

Reputation: 2128

Is it a bad idea to use indexOf inside loops?

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.

Upvotes: 23

Views: 12128

Answers (3)

Mo Hemati
Mo Hemati

Reputation: 281

based on the browser, the indexOf has different implementations (using graphs, trees, ...). So, the time complexity for each indexOf also differs. Though, what is clear is that implementing indexOf to have O(n) would be so naive and I don't think there is a browser to have it implements like a simple loop. Therefore, using indexOf in a for loop is not the same as using 2 nested for loops.

So, this one:

// could be O(n*m) which m is so small
// could be O(log n)
// or any other O(something) that is for sure smaller than O(n^2)
console.time('1')
firstArray.forEach(item => {
  secondArray.indexOf(item)
})
console.time('1')

is different than:

// has O(n^2)
console.time('2')
firstArray.forEach(item => {
  secondArray.forEach(secondItem => {
    // extra things to do here
  })
})
console.time('2')

Upvotes: 1

Marcus Handley
Marcus Handley

Reputation: 182

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.

Upvotes: 9

4lackof
4lackof

Reputation: 1390

To be honest, tl;dr. But, I did some speed tests of the various ways of checking for occurrences in a string (if that is your goal for using indexOf. If you are actually trying to get the position of the match, I personally don't know how to help you there). The ways I tested were:

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

(There are also the variants such as .search(), .lastIndexOf(), etc. Those 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 they are not loops, but show you that all are basically the same speed. And honestly, each do different things, depending on what you need (do you want to search by RegEx? Do you need to be pre ECMAScript 2015 compatible? etc. - I have not even listed all of them) is it really necessary to analyze it this much?

From my tests, sometimes indexOf() would win, sometimes one of the other ones would win.

Upvotes: 5

Related Questions