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
– SuperStormer, Commented Aug 11, 2022 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
– Brother58697, Commented Aug 11, 2022 at 17:38
How are you measuring the computational complexity of the running code? — ryanwebjackson
– ryanwebjackson, Commented Aug 11, 2022 at 17:39
Does this answer your question? Time complexity to check if a key exists in an object using "in" property — SuperStormer
– SuperStormer, Commented Aug 11, 2022 at 17:43

Nabeel Ahmed · Accepted Answer · 2022-08-11 17:52:46Z

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)

Wrong, key in frequencyCounter is O(1), as mentioned in the links I provided in the comment above.
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

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related