Search code examples
javascriptarraysbig-otraversal

What is the runtime given a nested loop?

I am trying to get better at coding, so after each hackerrank challenge, I check to see what other people have done so I can compare my code to theirs. One that came up as an interesting solution, that apparently works, is this:

function getMoneySpent (keyboards, drives, b) {
  return keyboards.reduce (
    (acc, curr) =>
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

console.log (getMoneySpent ([1, 20, 40], [5, 60, 7], 50));

It basically finds the maximum sum of two numbers (one from each array) that are <= a number (50 in this case). However, as I dissected the code it seems like there is two loops, a .reduce, and a .map with a .filter. Does that make this code O(n)^2? I'm pretty sure it would not pass the test cases if it were, as the arrays can be 1000 long, and the number (50) can be 10^6. Here's the link to the problem if you're interested.

So after all that my question is - is this code O(n)^2?

Solution

  • As far as I can see, it's actually 3•O(n)^2

    See below for reasoning:

    function getMoneySpent (keyboards, drives, b) {
                // O(n)
  return keyboards.reduce ( 
    (acc, curr) =>
        // O(n) +              O(n) +                  O(n)
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

    O(n) * (O(n) + O(n) + O(n))
O(n) * 3•O(n)
3•O(n)^2

    Math.max source code