What is the coplexity of my solution?

Question

I have the following computer problem:

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
 

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.
Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.
Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.
 

Constraints:

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

Summarizing I have to validate if a vector has a number that has its double.

I already have the solution that works:

var checkIfExist = function(arr) {
    const set = new Set();
    
    for(let i = 0; i < arr.length; i ++) {
      const currValue = arr[i];
      
      if(set.has(currValue)) {
        return true
      }
      set.add(currValue / 2);
      set.add(currValue * 2);
    }
  
  return false;
};

I have already solved the problem, but I am in doubt the complexity of my solution. I do not know if the set is O(1) in this case. For me the solution is O(N 2), but I am being told that it is O(N). Someone can explain to me the complexity of set.

Answer 1

The algorithm loop gives the answer. At worst, the output condition set.has(currValue) will never be true. This causes each element of the array to be visited at least once. And it could not be different, since it is impossible to guarantee that there is no pair (M, N) satisfying N = 2 * M without visiting each element.

for(let i = 0; i < arr.length; i ++) {
  const currValue = arr[i];
  
  if(set.has(currValue)) {
    return true
  }
  set.add(currValue / 2);
  set.add(currValue * 2);
}

I don’t know if the set is O(1) in this case.

Remember that a well-implemented Hashmap has an O(1) access time. Even if you assume that the Javascript Set guarantees this access time, and you need to check if the Set specification ensures this, you are accessing the Set up up to N times. Hence, O(N).