0

This is my first question on here and I hope I'm not breaking any rules. So, I'm fairly new at this programming thing, only been doing it for about 3 months now. I'm also teaching myself data structures and algorithms and I just started working through the easy problems on LeetCode today.

I have a question about calculating the Big O of a function specifically regarding maps.

        function twoSum(arr, target) {
          const len = arr.length;
    
          for (let i = 0; i < len; i++) {
            let currVal = arr[i];
            let comp = target - currVal;
          
            let firstIndex = arr.indexOf(currVal);
            let secondIndex = arr.indexOf(comp, firstIndex+1);
         
            if (secondIndex !== -1) {
              return [firstIndex, secondIndex];
            }
          }
        }

So initially, I was only counting the for loops when calculating Big O but then I found out that for this function, time complexity is actually O(n^2) because of indexOf.

Then I tried to solve this same problem using Maps so I wouldn't have to loop through the array twice.

        function twoSum(arr, target) {
          const indexValues = new Map();
          const result = [];
          const len = arr.length;
      
          for (let i = 0; i < len; i++) {
            let currVal = arr[i];
            let comp = target - currVal;
  
            indexValues.has(comp) ? result = [i, indexValues.get(comp)] : indexValues.set(currVal, i);
          }
    
          return result;
    
        }

Based on my understanding of maps, the time complexity for this should be O(n) but when I compare the two functions on LeetCode, they both get a runtime of 80 ms. So, long story short, does Map.has() method count as a loop similar to the indexOf function for some reason?

Thanks in advance!

CurlyLettuce
  • 1
  • 1
  • Does this answer your question? [es6 Map and Set complexity, v8 implementation](https://stackoverflow.com/questions/33611509/es6-map-and-set-complexity-v8-implementation) Perhaps more narrow than you're asking, but it should help. – Carcigenicate Jan 05 '21 at 19:56
  • No, it's `O(1)`. – Unmitigated Jan 05 '21 at 19:59
  • Thank you both! So the Big O for that function is indeed O(n). I'm still confused as to why LeetCode ranks both functions the same even though one has O(n^2) and the other has O(n) though. – CurlyLettuce Jan 05 '21 at 20:06
  • 1
    "*they both get a runtime of 80 ms*" - that doesn't mean they have different complexity. `O(n)` being better than `O(n²)` only holds above a certain threshold, so try a bigger input. – Bergi Jan 05 '21 at 20:17

0 Answers0