Big O: Common complexities

From worst to best:

Factorial: O(n!)

Example 1

TODO

Exponential: O(cⁿ)

Example 1

TODO

Polynomial: O(nᶜ)

Example 1

function operation(letters: string[]) {
  for (let i = 0; i < letters.length; i++) {
    for (let j = 0; j < letters.length; j++) {
      console.log(letters[i], letters[j])
    }
  }
}

operation(['a', 'b', 'c', 'd', 'e'])

// n = letters.length
// ---------------------------

// Time complexity: = O(n²)
// ---------------------------
// We have two nested loops

// Space complexity: = O(1).
// ---------------------------
// We don't store anything

Example 2

function operation(letters: string[]) {
  for (let i = 0; i < letters.length; i++) {
    for (let j = 0; j < letters.length; j++) {
      console.log(letters[i], letters[j])
    }
  }

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

operation(['a', 'b', 'c', 'd', 'e'])

// n = letters.length
// ---------------------------

// Time complexity: = O(n² + n) -> (On)
// ---------------------------
// We have two nested loops

// Space complexity: = O(1).
// ---------------------------
// We don't store anything

Linear: O(n)

Example 1

function operation(letters: string[]) {
  for (let i = 0; i < letters.length; i++) {
    console.log(i)
  }
}

operation(['a', 'b', 'c', 'd', 'e'])

// n = letters.length
// ---------------------------

// Time complexity: = O(n)
// ---------------------------
// We have a single loop

// Space complexity: = O(1).
// ---------------------------
// We don't store anything

Example 2

function arrayContains(array: string[], item: string) {
  return array.includes(item)
}

arrayContains(['red', 'green', 'blue', 'yellow'], 'red')

// n = words.length
// ---------------------------

// Time complexity: = O(n)
// ---------------------------
// Array.prototype.includes will check every element in `array` to see if it
// contains `item`

// Space complexity: = O(1).
// ---------------------------
// We don't store anything

Logarithmic: O(log(n)

Example 1

TODO

Constant: O(1)

Example 1

const colours = ['red', 'green', 'blue', 'yellow', 'black']
console.log(colours[3])