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.

Big O notion considers the worst-case running time of an algorithm.

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)

The idea here is that you must go through each element of n plus some of each element of n again. An example of this would be the quicksort algorithim.

function sort(list) {
  if (list.length <= 1) return list;
 
  var pivot = list.splice(Math.floor(list.length / 2), 1);
  var less = [], greater = [];
 
  while (list.length) {
    var item = list.shift();
    if (item <= pivot) {
      less.push(item);
    } else {
      greater.push(item);
    }
  }
  return sort(less).concat(pivot).concat(sort(greater));
};

O(log n) - logarithmic complexity

The idea here is that for some input n, we only need a small fraction of n to return the result. We can skip over the vast marjority of n's.

function find_n_in_sorted_list(n, list) {
  var middle = Math.floor(list.length / 2);
  if (middle > n) {
    for (var i = middle; i < list.length; i++) {
      if (list[i] === n) return n;
    }
  } else {
    for (var i = 0; i < middle; i++) {
      if (list[i] === n) return 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 instanceof Number;
}

O(n^2) - quadratic time

For n inputs, an algo operates on each input close to n times. A couple examples here might be to check for a number in common between two arrays or taking the sum of all pairs of numbers in an array.

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;
}

function sum_all_pairs(arr) {
  var result = [];
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length; j++) {
      if (i =! j) result.push(arr[i] + arr[j]);
    }
  }
  return result;
}