Big O notation (Asymptotic Notation)

The basic idea here is to give programmers a way to compare the performance of algorithms at a very high level in a language/platform/architecture independent way. This becomes particularly important when dealing with large inputs.

O(n) - linear time

For n inputs, an algorithm does roughly one operation for each input in n.

function in_array(val, arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] === val) return true;
  }
  return false;
}

O(n log n)

O(log n)

O(1) - constant time

The idea behind O(1) is that for any input the time is exactly the same.

function is_number(input) {
  return input instaceof Number;
}

O(n^2) - quadratic time

For n inputs, an algo operates on each input close to n times.

function has_number_in_common(arr1, arr2) {
  for (var i = 0; i < arr1.length; i++) {
    for (var j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) return true;
    }
  }
  return false;
}