 # Big O Notation in JavaScript

A quick overview of Big O Notation in JavaScript

21 November, 2022

8

8

1

Big O Notation, collectively called Bachmann-Landau notation or asymptotic notation, is a way to describe the performance of an algorithm. It is used to describe the worst-case scenario of an algorithm. It is used to compare the performance of different algorithms. It describes the implementation of an algorithm in terms of the input size.

Big O notation characterizes functions according to their growth rates: tasks with the same growth rate are considered to be of the same order. It is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify algorithms according to how their run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also called its order.

# Iteration

## For loop

```for (let i = 0; i < n; i++) {
console.log(i)
}for (let i = 0; i < n; i++) {  console.log(i)}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n) and the space complexity is O(1).

## While loop

```let i = 0
while (i < n) {
console.log(i)
i++
}let i = 0while (i < n) {  console.log(i)  i++}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n) and the space complexity is O(1).

## Do while loop

```let i = 0
do {
console.log(i)
i++
} while (i < n)let i = 0do {  console.log(i)  i++} while (i < n)
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n).

## Fibonacci (Iterative)

```function fibonacci(n) {
let arr = [0, 1]
for (let i = 2; i <= n; i++) {
arr.push(arr[i - 2] + arr[i - 1])
}
return arr[n]
}function fibonacci(n) {  let arr = [0, 1]  for (let i = 2; i <= n; i++) {    arr.push(arr[i - 2] + arr[i - 1])  }  return arr[n]}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n) and the space complexity is O(n). This is the second best fibonacci in terms of performance benchmark. The best one is using behold binet's formula, and even better when we precalculate the formula first.

# Recursion

## Factorial

```function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}function factorial(n) {  if (n === 0) {    return 1  }  return n * factorial(n - 1)}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n) and the space complexity is O(n).

## Fibonacci (Recursive)

```function fibonacci(n) {
if (n < 2) return n

return fibonacci(n - 1) + fibonacci(n - 2)
}function fibonacci(n) {  if (n < 2) return n
return fibonacci(n - 1) + fibonacci(n - 2)}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(2^n) and the space complexity is O(n). This things is called exponential time complexity. This is the worst fibonacci in terms of performance benchmark.

## Fibonacci (Recursive with Memoization)

```function fibonacci(n, cache = []) {
if (n === 0) return 0
if (n === 1) return 1
if (cache[n]) return cache[n]

cache[n] = fibonacci(n - 2, cache) + fibonacci(n - 1, cache)
return cache[n]
}function fibonacci(n, cache = []) {  if (n === 0) return 0  if (n === 1) return 1  if (cache[n]) return cache[n]
cache[n] = fibonacci(n - 2, cache) + fibonacci(n - 1, cache)  return cache[n]}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n) and the space complexity is O(n). This is the second worst fibonacci in terms of performance benchmark, but a bunch a lot better than without memoization.

# Searching

```function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i
}
}
return -1
}function linearSearch(arr, value) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === value) {      return i    }  }  return -1}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n times. The time complexity of this code is O(n).

```function binarySearch(arr, value) {
let start = 0
let end = arr.length - 1
let middle = Math.floor((start + end) / 2)
while (arr[middle] !== value && start <= end) {
if (value < arr[middle]) {
end = middle - 1
} else {
start = middle + 1
}
middle = Math.floor((start + end) / 2)
}
if (arr[middle] === value) {
return middle
}
return -1
}function binarySearch(arr, value) {  let start = 0  let end = arr.length - 1  let middle = Math.floor((start + end) / 2)  while (arr[middle] !== value && start <= end) {    if (value < arr[middle]) {      end = middle - 1    } else {      start = middle + 1    }    middle = Math.floor((start + end) / 2)  }  if (arr[middle] === value) {    return middle  }  return -1}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run log(n) times. The time complexity of this code is O(log(n)).

# Sorting

## Bubble sort

```function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}function bubbleSort(arr) {  for (let i = arr.length; i > 0; i--) {    for (let j = 0; j < i - 1; j++) {      if (arr[j] > arr[j + 1]) {        let temp = arr[j]        arr[j] = arr[j + 1]        arr[j + 1] = temp      }    }  }  return arr}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n^2 times. The time complexity of this code is O(n^2).

## Selection sort

```function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j
}
}
if (i !== lowest) {
let temp = arr[i]
arr[i] = arr[lowest]
arr[lowest] = temp
}
}
return arr
}function selectionSort(arr) {  for (let i = 0; i < arr.length; i++) {    let lowest = i    for (let j = i + 1; j < arr.length; j++) {      if (arr[j] < arr[lowest]) {        lowest = j      }    }    if (i !== lowest) {      let temp = arr[i]      arr[i] = arr[lowest]      arr[lowest] = temp    }  }  return arr}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n^2 times. The time complexity of this code is O(n^2).

## Insertion sort

```function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j]
}
arr[j + 1] = currentVal
}
return arr
}function insertionSort(arr) {  for (let i = 1; i < arr.length; i++) {    let currentVal = arr[i]    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {      arr[j + 1] = arr[j]    }    arr[j + 1] = currentVal  }  return arr}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n^2 times. The time complexity of this code is O(n^2).

## Merge sort

```function mergeSort(arr) {
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
let left = mergeSort(arr.slice(0, mid))
let right = mergeSort(arr.slice(mid))
return merge(left, right)
}

function merge(left, right) {
let results = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
results.push(left[i])
i++
} else {
results.push(right[j])
j++
}
}
while (i < left.length) {
results.push(left[i])
i++
}
while (j < right.length) {
results.push(right[j])
j++
}
return results
}function mergeSort(arr) {  if (arr.length <= 1) return arr  let mid = Math.floor(arr.length / 2)  let left = mergeSort(arr.slice(0, mid))  let right = mergeSort(arr.slice(mid))  return merge(left, right)}
function merge(left, right) {  let results = []  let i = 0  let j = 0  while (i < left.length && j < right.length) {    if (left[i] < right[j]) {      results.push(left[i])      i++    } else {      results.push(right[j])      j++    }  }  while (i < left.length) {    results.push(left[i])    i++  }  while (j < right.length) {    results.push(right[j])    j++  }  return results}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n log(n) times. The time complexity of this code is O(n log(n)).

## Quick sort

```function pivot(arr, start = 0, end = arr.length + 1) {
let pivot = arr[start]
let swapIdx = start
function swap(array, i, j) {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
for (let i = start + 1; i < arr.length; i++) {
if (pivot > arr[i]) {
swapIdx++
swap(arr, swapIdx, i)
}
}
swap(arr, start, swapIdx)
return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right)
quickSort(arr, left, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, right)
}
return arr
}function pivot(arr, start = 0, end = arr.length + 1) {  let pivot = arr[start]  let swapIdx = start  function swap(array, i, j) {    let temp = array[i]    array[i] = array[j]    array[j] = temp  }  for (let i = start + 1; i < arr.length; i++) {    if (pivot > arr[i]) {      swapIdx++      swap(arr, swapIdx, i)    }  }  swap(arr, start, swapIdx)  return swapIdx}
function quickSort(arr, left = 0, right = arr.length - 1) {  if (left < right) {    let pivotIndex = pivot(arr, left, right)    quickSort(arr, left, pivotIndex - 1)    quickSort(arr, pivotIndex + 1, right)  }  return arr}
/**
* Reset the text fill color so that placeholder is visible
*/
.npm__react-simple-code-editor__textarea:empty {
-webkit-text-fill-color: inherit !important;
}

/**
* Hack to apply on some CSS on IE10 and IE11
*/
@media all and (-ms-high-contrast: none), (-ms-high-contrast: active) {
/**
* IE doesn't support '-webkit-text-fill-color'
* So we use 'color: transparent' to make the text transparent on IE
* Unlike other browsers, it doesn't affect caret color in IE
*/
.npm__react-simple-code-editor__textarea {
color: transparent !important;
}

.npm__react-simple-code-editor__textarea::selection {
background-color: #accef7 !important;
color: transparent !important;
}
}
```

The above code will run n log(n) times. The best case time complexity of quick sort is O(n log(n)) and the worst case time complexity of quick sort is O(n^2) with average case time complexity of O(n log(n)). The space complexity is O(n).

# Tips for Big O

• Arithmetic operations are constant
• Variable assignment is constant
• Accessing elements in an array (by index) or object (by key) is constant
• In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

# Resources

javascript
develevate
bestpractices
hotintech
toolstipstricks

8

8 