# Big O Notation in JavaScript

21 November, 2022

8

8

Contributors

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

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

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

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

## Fibonacci (Iterative)

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

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)

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)

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

## Linear search

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

## Binary search

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

# Sorting

## Bubble sort

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

## Selection sort

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

## Insertion sort

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

## Merge sort

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

## Quick sort

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