Cacher is the code snippet organizer for pro developers

https://medium.com/@bretcameron/ace-your-coding-interview-by-understanding-big-o-notation-and-write-faster-code-6b60bd498040

At its most basic level, Big O Notation provides us with a quick way to assess the speed or, more properly, the performance of an algorithm.

It measures how quickly the run-time grows relative to the input, as the input increases.

O(1)

This represents an algorithm whose run-time is fixed. No matter the amount of data you feed in, the algorithm will always take the same amount of time.

In the following example, we pass an array to a function. It doesn’t matter whether the array has 1 entry or 1,000 it will always take the same amount of time, because it’s simply returning the very first value.

We call that O(1), and any function that spits out one value regardless of the input size can be described as having a performance of O(1).

function(array) {
  return array[0];
}

O(N) — Linear Time

This is the equivalent of going through all your emails by hand. As the length of the array increases, the amount of processing required increases at the same rate.

In this function, every item in an array is printed straight to the console. As the size of the array increases, the number of times console.log() is called increases by exactly the same amount.

function logArray(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
}

Note that Big O Notation is based on the maximum possible iterations. Because of that, the following function still has an algorithmic efficiency of O(N), even though the function could finish early; that’s why some people see it as a measure of the “worst case scenario”.

function findTheMeaningOfLife(array){
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 42) {
      return i;
    }
  }
}

O(N²) — Quadratic Time

An algorithm with an efficiency of O(N²) increases at twice the relative rate of O(N). I’ll demonstrate using console.log.

Let’s say we have an array of three numbers: array = [1, 2, 3].

If we pass that to the function logArray() above, then it will simply print out the numbers 1, 2 and 3.

But what about this function?

function(array){
  for (let i = 0; i < array.length; i++){
    for (let j = 0; j < array.length; j++){
      console.log(array[j]);
    }
  }
}

This will print 1 2 3 1 2 3 1 2 3 to the console.

That’s 9 numbers, compared to the 3 printed by logArray. And so it follows that 3² = 9, and this function has a performance of O(N²).

If two nested loops gives us O(N²), it follows that three nested loops gives us O(N³), four nested loops gives us O(N⁴), and so on.