The idea behind big O notation

big-0.md

Big O notation is for talking about how long an algorithm takes to run

It's how we compare the efficiency of different approaches to a problem.

With big O notation we express the runtime in terms of how quickly it grows relative to the input, as the input gets large.

1. how quickly the runtime grows—It's hard to pin down the exact runtime of an algorithm. It depends on the speed of the processor, what else the computer is running, etc. So instead of talking about the runtime directly, we use big O notation to talk about how quickly the runtime grows.

2. relative to the input—If we were measuring our runtime directly, we could express our speed in seconds. Since we're measuring how quickly our runtime grows, we use the size of the input, which we call "n." So we can say things like the runtime grows "on the order of the size of the input" (O(n) or "on the order of the square of the size of the input" (O(n²).

3. as the input gets arbitrarily large—Our algorithm may have steps that seem expensive when n is small but are eclipsed eventually by other steps as n gets huge. For big O analysis, we care most about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as n gets very large.

Let's look at some examples:

function printFirstItem(items) {
  console.log(items[0]);
}

This function runs in O(1) time (or "constant time") relative to its input. The input array could be 1 item or 1,000 items, but this function would still just require one "step."

function printAllItems(items) {
  items.forEach(item => {
    console.log(item);
  });
}

This function runs in O(n) time (or "linear time"), where nn is the number of items in the array. If the array has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times.

function printAllPossibleOrderedPairs(items) {
  items.forEach(firstItem => {
    items.forEach(secondItem => {
      console.log(firstItem, secondItem);
    });
  });
}

Here we're nesting two loops. If our array has nn items, our outer loop runs nn times and our inner loop runs nn times for each iteration of the outer loop, giving us n² total prints. Thus this function runs in O(n²) time (or "quadratic time"). If the array has 10 items, we have to print 100 times. If it has 1,000 items, we have to print 1,000,000 times.

N could be the actual input, or the size of the input

Both of these functions have O(n) runtime, even though one takes an integer as its input and the other takes an array:

  function sayHiNTimes(n) {
  for (let i = 0; i < n; i++) {
    console.log('hi');
  }
}

function printAllItems(items) {
  items.forEach(item => {
    console.log(item);
  });
}

So sometimes n is an actual number that's an input to our function, and other times nn is the number of items in an input array (or an input map, or an input object, etc.).

Don't need the constants

When you're calculating the big O complexity of something, you just throw out the constants.

function printAllItemsTwice(items) {
  items.forEach(item => {
    console.log(item);
  });

  // Another separate loop
  items.forEach(item => {
    console.log(item);
  });
}

This is O(2n), which we just call O(n).

function printAllNumbersThenAllPairSums(numbers) {

  // first loop (n)
  numbers.forEach(number => {
    console.log(number);
  });

  // second loop (2n)
  numbers.forEach(firstNumber => {
    // second loop (2n<sup>2</sup>)
    numbers.forEach(secondNumber => {
      console.log(firstNumber + secondNumber);
    });
  });
}

Here our runtime is O(n + n²), which we just call O(n²).

We are usually talking about "worse case"

Often this "worst case" stipulation is implied. But sometimes you can impress your interviewer by saying it explicitly.

Sometimes the worst case runtime is significantly worse than the best case runtime:

function contains(haystack, needle) {

  // Does the haystack contain the needle?
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle) {
      return true;
    }
  }

  return false;
}

Here we might have 100 items in our haystack, but the first item might be the needle, in which case we would return in just 1 iteration of our loop.

In general we'd say this is O(n) runtime and the "worst case" part would be implied. But to be more specific we could say this is worst case O(n) and best case O(1) runtime. For some algorithms we can also make rigorous statements about the "average case" runtime.

Space complexity

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or "space complexity") is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we're allocating.

This function takes O(1)O(1) space (we use a fixed number of variables):

function sayHiNTimes(n) {
  for (let i = 0; i < n; i++) {
    console.log('hi');
  }
}

This function takes O(n) space (the size of hiArray scales with the size of the input):

function arrayOfHiNTimes(n) {
  const hiArray = [];
  for (let i = 0; i < n; i++) {
    hiArray[i] = 'hi';
  }
  return hiArray;
}

Usually when we talk about space complexity, we're talking about additional space, so we don't include space taken up by the inputs. For example, this function takes constant space even though the input has nn items:

  function getLargestItem(items) {
  let largest = -Number.MAX_VALUE;
  items.forEach(item => {
    if (item > largest) {
      largest = item;
    }
  });
  return largest;
}

Sometimes there's a tradeoff between saving time and saving space, so you have to decide which one you're optimizing for.