Does the JavaScript "in" operator execute a loop under the hood?

Question

I was studying some solutions to common algorithms and I ran across something that I am curious about. I tried to find the answer myself by googling and looking at some of the specifications but I am unable to find the answer to my question. The below algorithm basically checks to see if every item in the first array has a corresponding item squared in the second array. The naive solution (as they say) would have some sort of nested loop and be considered O(n2). The person who wrote the solution below said this is O(n).

I don't understand how this can be O(n) because he is using the Javascript "in" operator inside of his loop. As far as I can tell that operator checks to see if the value it's comparing exists in the object. How does it do that if it is not looping through the object under the hood? Is this really a linear time complexity?

function same(arr1, arr2) {

  if (arr1.length !== arr2.length) {
    return;
  }

  let frequencyMap1 = {};
  let frequencyMap2 = {};

  for (let val of arr1) {
    frequencyMap1[val] = (frequencyMap1[val] || 0) + 1;
  }

  for (let val of arr2) {
    frequencyMap2[val] = (frequencyMap2[val] || 0) + 1;
  }

  for (let key in frequencyMap1) {
    if (!(key ** 2 in frequencyMap2)) {
      return false;
    }

    if (frequencyMap2[key ** 2] !== frequencyMap1[key]) {
      return false
    }
  }

  return true;
}

console.log(same([1, 2, 3], [1, 4, 9])); // true

It basically is squaring the value from the first array. I guess you could think of it as key * key. — Aaron, Mar 09 '19 at 14:57
@NinaScholz that's the [exponentiation operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Arithmetic_Operators#Exponentiation_(**)) introduced in ES2016 — Patrick Roberts, Mar 09 '19 at 14:57
@nina `The below algorithm basically checks to see if every item in the first array has a corresponding item squared in the second array` — Jonas Wilms, Mar 09 '19 at 15:00
I don't know, it wasn't my solution. Im just trying to understand Javascript better. But it was odd to me as well. :) — Aaron, Mar 09 '19 at 15:00
@JonasWilms, oh, right, thanks. i should read the text, too. it is too much prosa for me. — Nina Scholz, Mar 09 '19 at 15:02

zmag · Accepted Answer · 2019-03-09T15:14:38.473

6

Finding a key in an object is O(1). for .. in and just only in operator is different.

No matter how many keys are in an object, you can access it in constant time. Object or Map has a hash table to find a key.

edited Mar 09 '19 at 15:14

answered Mar 09 '19 at 14:57

zmag

7,825
12
32
42

I understand that finding the value in a key/value is constant. I didn't know the same mechanism worked for finding the key. – Aaron Mar 09 '19 at 14:58
3

To be a little more clear, `for...in` is O(n) and just `in` is O(1). – Scott Rudiger Mar 09 '19 at 15:00
1

@aaron hashtables are usually a list of key-value pairs that are stored in an array based on the hashed key. To get the value from a key, the hash is generated, a search is done at the keys hash position (as hashes might collide) , and the pair with the wanted key gets found, the value gets returned. `in` does the same thing, just that it doesnt return a value. – Jonas Wilms Mar 09 '19 at 15:04
@Jonas, thank you. – Aaron Mar 09 '19 at 15:06

score 2 · Answer 2 · answered Mar 09 '19 at 14:59

2

It depends. Lookup time on objects is not guaranteed by spec, so this could be O(n²) worst case. However most engines will represent objects as hashtables if you use a lot of different keys, and then the lookup time is O(1) and the algorithm runs at O(n).

answered Mar 09 '19 at 14:59

Jonas Wilms

132,000
20
149
151

1

On hashtables, O(1) is just the _average_ case. The worst case is still O(n), so hypothetically you could still be dealing with a O(n²) worst case when using a `for...in` loop. – Patrick Roberts Mar 09 '19 at 15:04
@patrick that would assume that all hashes collide, and I would bet that this does not happen on all keys, so I think we can safely assume that this "hypothetical" case does never happen. – Jonas Wilms Mar 09 '19 at 15:06
2

I'm just pointing out there is a distinct possibility, however slim. In contrast, arrays and typically object prototypes are stored in sequential memory, so for those types of objects, access truly is O(1) in all cases, as opposed to the objects backed by hashtables. – Patrick Roberts Mar 09 '19 at 15:34

T.J. Crowder · Answer 3 · 2019-03-09T15:03:13.927

Different answers for in and for-in:

The in operator looks in an object (and if necessary, its prototype, and its prototype, etc.) to see if the object has a property with a given name. In any even half-decent JavaScript engine, that's not going to involve a loop other than the loop through the prototype chain (and on a good one, not even that, because on a good JavaScript engine objects get implemented as JIT classes so they know their structure).

for-in loops loop through the names of the enumerable properties in an object and its prototypes. So naturally, that involves a loop (possibly nested, given the prototype chain is involved).

Does the JavaScript "in" operator execute a loop under the hood?

3 Answers3

Linked

Related