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 the loop Resources Big O Cheat Sheet Big O Notation Big O Notation Originally published . here
