## Question:

The number of elements reaches 100000 and I have to compare it with another vector of 100000, how can I do this with a very high performance gain

How I'm comparing the vectors

```
for(i = 0; i < teste; i++)
{
for(j = 0; j < teste; j++)
{
if(indice[i] == aux[j])
{
cont++;
}
}
}
```

## Answer:

You can try creating a *hash* array, for example

```
char hash[0x7FFFFFFF];
```

if any positive integers are possible.

Initialize the vector,

```
for (int i = 0; i < 0x7FFFFFFF; ++i)
{
hash[i] = 0;
}
```

Iterate over one of your original vectors and use the *hash* to know that that number exists in this vector:

```
for (int i = 0; i < teste; ++i)
{
hash[indice[i]] = 1;
}
```

Then iterate over the second vector, incrementing `cont`

if the *hash* is already filled,

```
for (int i = 0; i < teste; ++i)
{
if (hash[aux[i]])
{
++cont;
}
}
```

That way the complexity becomes O(n), instead of O(n^2), which was your case.

The problem now is that too much RAM is used. 1GB RAM minimum, just for the *hash* vector…

So there is a tradeoff between algorithmic complexity and spatial complexity, which must always be taken into account.