Big O Notation in JavaScript
Imamuzzaki Abu Salam
Posted on November 21, 2022
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)
}
The above code will run n times. The time complexity of this code is O(n).
While loop
let i = 0
while (i < n) {
console.log(i)
i++
}
The above code will run n times. The time complexity of this code is O(n).
Do while loop
let i = 0
do {
console.log(i)
i++
} while (i < n)
The above code will run n times. The time complexity of this code is O(n).
Recursion
Factorial
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
The above code will run n times. The time complexity of this code is O(n).
Fibonacci
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
The above code will run n times. The time complexity of this code is O(n).
Searching
Linear search
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i
}
}
return -1
}
The above code will run n times. The time complexity of this code is O(n).
Binary search
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
}
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
}
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
}
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
}
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
}
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
}
The above code will run n log(n) times. The time complexity of this code is O(n log(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
Posted on November 21, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
October 24, 2024