Big O Notation

Big O Notation refers to time and space complexity. Basically, it is a fancy way of saying how long an algorithm will take and how much memory space it will use. This week we will go over the different types and some examples. I will be referring to time, but this also applies to memory space as well.

1. Constant Time or O(1)- Size doesn’t matter for constant time. It will always take the same amount of time no matter the size of the input. An example of this would be calling .shift() on an array or accessing a specific element of an array.

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

2. Logarithmic Time or O(log(n)) — Time is directly proportional to the size of the input. This is common in binary trees. The below example would be O(log(2)) time, because we are multiplying i by 2. This differs from linear time because of how i is being incremented.

function printString(){
   for(let i = 1; i <= 10; i *=2){
      console.log('hi')
   }
}

3. Linear O(n) — An example of linear time would be iterating through an array. Please note it is still O(n) time if you are asked to iterate through only half. Also, if there are two different arrays and you have to iterate through them separately, but within the same function, it is still considered linear time.

function findTwos(array){
   let result = []
   for(let element of array){
      if(element === 2){
         result.push(element)
      }
   }
   return result.length
}

4. Quasilinear O(log(n)*n) —As you would expect, this is a combination of linear and logarithmic time. In this example, the first loop is linear time while the second loop is logarithmic time.

function printString(){
   for(let i = 0; i < 3; i++){
      for(let j = 1; j < 3; j = j * 2){
         console.log("hej")
      }
   }
}

5. Quadratic or O(n2) — An example of this would be a nested loop. Every element of an array has to be compared to every element of another array. Remember the Pyramid Problem I blogged about a few weeks ago? This is quadratic time.

function pyramid(n) {
  const midpoint = Math.floor((2*n-1) / 2)
  for (let row = 0; row < n; row++){
    let level = ''
      for (let column = 0; column < 2*n-1; column++){
        if (midpoint - row <= column && midpoint + row >= column) {
          level += '#'
        } else {
          level +=' '
        }
      }
    console.log(level)
  }
}

6. Exponential or O(2n) — If you add an extra element, the processing time doubles. This is not good! If you ever find yourself using exponential time, try to find a solution that has a better time.

Once you get to know these types, you will start recognizing and improving them when you code every day.