Nested For in loops are O(n) but should be O(n^2)?

Question

const anagram = (str1, str2) => {
    str1 = str1.split('');
    str2 = str2.split('');
    
   let frequencyCounter1 = {};
   let frequencyCounter2 = {};

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

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

   for(let key in frequencyCounter1) {

       if(!(key in frequencyCounter2)) {
           return false;
       }

       if(frequencyCounter1[key] !== frequencyCounter2[key]) {
           return false;
       }
   }

    return true;
}

anagram('racecar', 'racecar');

This challenge asks to use a frequency counter pattern to test if str2 is an anagram of str1. The answer provided is supposedly O(n). How is this possible with this if statement:

if(!(key in frequencyCounter2)) {
           return false;
       }

Wouldn't this suggest you are going to loop through the object to make sure it contains that key, therefore you have nested loops and O(n^2)?

@Brother58697 That's not what OP is referring to - they're talking about `key in frequencyCounter2` (presumably) using an implicit loop. — SuperStormer, Aug 11 '22 at 17:37
Building frequencyCounter2 is O(n) and looping over it afterwards is is O(n) so the overall time complexity is O(n). — Brother58697, Aug 11 '22 at 17:38
How are you measuring the computational complexity of the running code? — ryanwebjackson, Aug 11 '22 at 17:39
Does this answer your question? [Time complexity to check if a key exists in an object using "in" property](https://stackoverflow.com/questions/64207312/time-complexity-to-check-if-a-key-exists-in-an-object-using-in-property) — SuperStormer, Aug 11 '22 at 17:43
Also related: https://stackoverflow.com/questions/6586670/how-does-javascript-vm-implements-object-property-access-is-it-hashtable https://stackoverflow.com/questions/55078564/does-the-javascript-in-operator-execute-a-loop-under-the-hood https://stackoverflow.com/questions/34292087/is-there-anything-that-guarantees-constant-time-for-accessing-a-property-of-an-o https://stackoverflow.com/questions/12241676/javascript-objects-as-hashes-is-the-complexity-greater-than-o1 — SuperStormer, Aug 11 '22 at 17:43
@Brother58697 That's **not** what OP is asking about. They are asking about the contains check within the last loop, not the first 2 loops. — SuperStormer, Aug 11 '22 at 17:44
FWIW, I know the question isn't about if the function works or not. But it doesn't work as is. If I add a character to the second argument, it still returns true. — imvain2, Aug 11 '22 at 17:47
I understand what you mean now, I didn't catch it at first. In that case, your links were pretty helpful in understanding how JS handles `if(key in obj)` which I didn't even know existed haha. Before reading I'd just assume it's O(1) like a dictionary, and it looks like that's around the case. — Brother58697, Aug 11 '22 at 17:47

Nabeel Ahmed · Accepted Answer · 2022-08-11T17:52:46.810

3

it's actually O(n) because

for(let key in frequencyCounter1) {

       if(!(key in frequencyCounter2)) {
           return false;
       }

       if(frequencyCounter1[key] !== frequencyCounter2[key]) {
           return false;
       }
   }

you are iterating over frequencyCounter1 O(n) and then you find each iteration key from frequencyCounter1 in frequencyCounter2 and js objects are basically key-value pairs so finding a key will take O(1). hence the total time complexity is O(n)

edited Aug 11 '22 at 17:52

answered Aug 11 '22 at 17:47

Nabeel Ahmed

130
7

3

Wrong, `key in frequencyCounter` is O(1), as mentioned in the links I provided in the comment above. – SuperStormer Aug 11 '22 at 17:47
2

I'm sorry I did update my answer. Thanks for hopping I usually code in java so I was a bit confused between the {} symbol. like is it array or object – Nabeel Ahmed Aug 11 '22 at 17:54

Nested For in loops are O(n) but should be O(n^2)?

1 Answers1