CODEWITHSUNDEEP
javascripttime
Hozackeno
Hozackeno

Reputation: 1

Question about JavaScript Code Time Complexity

var findDisappearedNumbers = function(nums) {
    
    const numberSet = new Set();

    for(let i = 1; i < nums.length + 1; i++) {
        numberSet.add(i);
    }

    nums.forEach((element) => {
        if(numberSet.has(element)) {
            numberSet.delete(element);
        }
    });

    return Array.from(numberSet);
};

Above is a solution for leetcode problem 448. https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/

Apparently the time complexity of the program is O(n). This is what I dont understand, shouldn't it be O(n^2) since you iterate nums once to populate numberSet, then you iterate over nums again to check duplicates?

So both the for loop and nums.forEach are both O(n) making it overall O(n^2)?

Upvotes: 0

Views: 62

Answers (3)

vol.qiu
vol.qiu

Reputation: 22

This solution is easy to understand;

var findDisappearedNumbers = function (nums) {
  const numberSet = new Set(nums);

  let result = [];

  for (let i = 1; i < nums.length + 1; i++) {
    if (!numberSet.has(i + 1)) {
      result.push(i);
    }
  }

  return result;
};

Upvotes: -1

Benn27
Benn27

Reputation: 21

The time complexity is O(N) and not O(n^2) because you iterate the nums twice, which means that the time complexity is O(2N) which you can just simplify into O(N). The time complexity will be O(n^2) if you iterate the nums within an iteration of nums like:

for(let i = 1; i < nums.length + 1; i++) {
   for(let j = 1; j < nums.length + 1; j++){
      // code
   }
}

Hope this helps

Upvotes: 2

Brandon
Brandon

Reputation: 416

Since there are two loops, the time complexity would technically be O(2n). However, with asymptotic analysis, we drop constant coefficients and lesser terms. So O(2n) is equivalent to O(n).

If the loops were nested, the runtime would be O(n^2). For example:

for (let i = 1; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    // Do something
  }
}

Upvotes: 0

Related Questions