-7

Find if the two arrays contain a similar property or value.

const one =[1,2,3,4,5]
const two = [5,6,7,8] 

// a double loop that solves this problem 
O(n^2)

VS

two.some(item => one.includes(item))
// this is more efficient than the double loop method 
// but behind the scenes isnt javascript just looping ?
// why is this more performant ? 
// and is the big O  of this O(n)?
kathmandu
  • 41
  • 9
  • "*this is more efficient than the double loop method*" - what makes you think that? You're right, it's still two nested loops, just written differently. – Bergi Nov 05 '21 at 01:08
  • The second will have "short-circuiting", i.e., it will stop as soon as it finds a result. The first will as well if you implement it correctly. As for *"why is this more performant"* Big-O doesn't measure true performance in the way you appear to think it does. – Nick is tired Nov 05 '21 at 01:11

1 Answers1

1

If your

a double loop that solves this problem

breaks out of the loops as soon as a match is found, then both methods are similarly inefficient - they both require iterating over all of N elements M times, worst-case, where N is the length of one array and M is the length of the other. (So, O(n * m), or O(n^2), depending on how you want to specify the lengths of the inputs.)

The advantage to the second method

two.some(item => one.includes(item))

is that it's a lot more readable than using for loops. It's not more performant - the opposite is true, for loops are generally faster than array methods.

If you wanted to reduce the complexity to O(n), instead of iterating over the second array inside a loop, use a Set lookup inside the loop, which is much faster:

const oneSet = new Set(one);
return two.some(item => oneSet.has(item));

because set lookup is sublinear, and generally O(1) - resulting in an overall complexity of O(n).

CertainPerformance
  • 356,069
  • 52
  • 309
  • 320