What is Big O Notation?

Big O notation is used in Computer Science to describe the time complexity of an algorithm. The best algorithms will execute the fastest and have the simplest complexity.

Algorithms don’t always perform the same and may vary based on the data they are supplied. While in some cases they will execute quickly, in other cases they will execute slowly, even with the same number of elements to deal with.

In these examples, the base time is 1 element = 1ms.

O(1)
arr[arr.length - 1]
  • 1000 elements = 1ms

Constant time complexity. No matter how many elements the array has, it will theoretically take (excluding real-world variation) the same amount of time to execute.

O(N)
arr.filter(fn)
  • 1000 elements = 1000ms

Linear time complexity. The execution time will increase linearly with the number of elements the array has. If the array has 1000 elements and the function takes 1ms to execute, 7000 elements will take 7ms to execute. This is because the function must iterate through all elements of the array before returning a result.

O(1, N)
arr.some(fn)
  • 1000 elements = 1ms <= x <= 1000ms

The execution time varies depending on the data supplied to the function, it may return very early or very late. The best case here is O(1) and the worst case is O(N).

O(NlogN)
arr.sort(fn)
  • 1000 elements ~= 10000ms

Browsers usually implement the quicksort algorithm for the sort() method and the average time complexity of quicksort is O(NlgN). This is very efficient for large collections.

O(N^2)
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    // ...
  }
}
  • 1000 elements = 1000000ms

The execution time rises quadratically with the number of elements. Usually the result of nesting loops.

O(N!)
const permutations = arr => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [
          item,
          ...val
        ])
      ),
    []
  )
}
  • 1000 elements = Infinity (practically) ms

The execution time rises extremely fast with even just 1 addition to the array.

Extra info

  • Be wary of nesting loops as execution time increases exponentially.
Additional links

Leave a Reply

Your email address will not be published. Required fields are marked *

*