CODEWITHSUNDEEP
javascriptbig-o
plus
plus

Reputation: 365

Which is the runtime complexity of this function?

This is the first time that I heard about big O, so I'm not clear at all, for my personal opinion this is a O(n^2), because its using filter for each object then includes for each object of the another array..

function subset(a, b) {
  const result = a.filter(a => b.includes(a));
  return (result.length == b.length) ? true : false;
}

const array1 = ["a", "b", "c", "d", "e", "f", "g"];

const array2 = ["a", "b", "e", "g", "e"];

const isSubset = subset(array1, array2);

console.log(isSubset);

Upvotes: 1

Views: 107

Answers (1)

BarT
BarT

Reputation: 347

array1.size = n

array2.size = m

if we translate it to pseudo code:

for each object1 in array1.size:
   for each object2 in array2.size:
         object2.includes(object1)

so the complexity is O(n*m).

Upvotes: 2

Related Questions