Big O Complexity algorithm

Question

I'm just learning about Big O notation, and I've been going through a few thought puzzles, and I just thought I'd verify with people whether I'm thinking through things correctly.

In Javascript would this be considered an O(n) time solution for a search for common items through two arrays? Or does the language perform lookups within an object and iterate through n elements within the object the same way it iterates through an array?

function findCommon (input, input2){
  var key = {};
  var out = [];
  for(var i=0; i<input.length; i++){
    key[input[i]] = true;
  }
  for(var j=0; j<input2.length; j++){
    if(key[input2[j]] == true){
      out.push(input2[j]);
    }
  }
  return out;
} 

findCommon([1, 2, 4, 6, 7], [3, 4, 5, 7]) -->[4, 7]

Answer 1

Let m be the length of input and n be the length of input2. The complexity of the first loop is O(m) and the complexity of the second one is O(n). Whenever you are facing sequential code, complexities are summed up (they would've been multiplied if the loops were nested instead of sequential), giving us a total O(m + n) and that is the exact upper bound and is obviously linear in the size of the arguments.

Now, m + n <= 2 * max(m, n) so you may say that the function is also O(2 * max(m, n)) but we can of course drop the constant so that gives us O(max(m, n)). Let us assume that n is always greater than m (it's not a big deal as it doesn't change much). That gives us O(n), so indeed you can say that the algorithm is O(n) but a more precise notation would be O(m + n).

Answer 2

Your function consist of two O(n) complexities. Therefore, total complexity of your function is O(n). As mentioned in comments, I would like to clarify that you have two different O(n) and O(m) which are not equal to O(2n) (however, you would still drop all constants). But it doesn't matter in your case, since complexity depends not on size of m or n, but on complexity of structure ( single for loop in your case)