CODEWITHSUNDEEP
javascriptarraysalgorithm
Gorakh Nath
Gorakh Nath

Reputation: 9858

What will be Time Complexity if we use include function inside the some function of array

As we know that Array.prototype.some() and Array.prototype.includes() has time complexity of o(n). Now I want to know that what if I will use include inside some method. The time complexity will be linear or quadratic?

function checkDublicate (arr1, arr2) {
return arr1.some(item => arr2.includes(item));
}

Upvotes: 0

Views: 1053

Answers (3)

Mayank_MP5
Mayank_MP5

Reputation: 313

It will be Quadratic TC ie. O(mn)

for array of length n

  • some() has TC of O(n)
  • includes() has TC of O(n)

In your case, You are using two nested loops logic wise so Time Complexity will be the product of both TC

TC(checkDublicate) = TC(some(arr1.length)) * TC(includes(arr2.length))

TC(checkDublicate) = O(arr1.length * arr2.length)

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8111

Considering the worst case scenario, if arr2 has no items from arr1, all n elements will be searched in arr2, with each search having O(n) complexity. Overall complexity will be O(n^2) (assuming n elements in either array).

Upvotes: 1

Parzh from Ukraine
Parzh from Ukraine

Reputation: 9903

It's O(mn), where m is arr1.length and n is arr2.length.

Upvotes: 2

Related Questions