What is the real complexity of this algorithm?

Question

Algorithms

The question is essentially theoretical, but it also has a practical meaning.

I will set it immediately for two languages, and I will give an abstract example.

Let's say we are given a list of adishers: and an associative array is given:
const ids = List(['id1', 'id2', 'id3']);

const data = Map({
  id1: someData,
  id2: someData,
   ...
  idN: someData
});

Looking through one project, I met a lot of such solutions there:

function getNeedData() {
  return data.filter((item) => ids.includes(item.get("id")));
}

It seemed strange to me. Instead of directly getting data from the data array by their keys, by iterating the ids array, here the data array is iterated, and in the called function iteration (implicitly) over ids again takes place.

I decided to look into the back part, it seems like they are more reverent about the performance of algorithms - and there is the same thing - only instead of includes - contains. As far as I understand - the essence is the same.

So here I have a doubt crept in - and maybe it should be?

As I understand it, filter iterates over the entire array, and includes does the same, and somewhere under the hood there is an iterator some, i.e. includes will loop through the array to the middle.

On average, you will have to do data.size * (ids.size / 2) iterations if you use the above algorithm. Whereas the same result can be achieved in ids.size iterations by iterating over ids. I'm not even talking about the fact that includes implies some kind of comparison, which in the general case can be very expensive, while getting from data by keys and nothing needs to be compared.

But maybe I'm misunderstanding something?

What is the real complexity of this algorithm for JS and JAVA and is it the right pattern?

Answer 1

Pretty common mistake. It is treated or by turning the logic around, as you noticed - go through the list of ids and see if there is one in data.
An even better option is to use some kind of set in ids instead of a list. This will work really fast if ids is long and data is short.