cover-img

21 November, 2022

Big O Notation in JavaScript

A quick overview of Big O Notation in JavaScript

Contributors

Imamuzzaki Abu Salam

7

7

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


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

While loop


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

Do while loop


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

Recursion

Factorial


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

Fibonacci


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

Searching


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


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 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

javascript
develevate
bestpractices
hotintech
toolstipstricks

7

7

1

Imamuzzaki Abu Salam
Frontend Engineer | Cybersecurity, ML, and OSS Enthusiast

More Shows

Imamuzzaki Abu Salam

Imamuzzaki Abu Salam

@imbios

Frontend Engineer | Cybersecurity, ML, and OSS Enthusiast

Tags

javascript
develevate
bestpractices
hotintech
toolstipstricks

More on Showwcase