Big-O Cheat Sheet

JavaScript, Algorithm · Jan 8, 2023

Big-O notation, represents an algorithm's worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm, allowing you to measure its efficiency and performance. Below you can find a chart that illustrates Big-O complexity:

Big-O Complexity Chart

Simply put, O(1) stands for constant time complexity, which is the most efficient, while O(n!) stands for factorial time complexity, which is the least efficient. The n in the complexity represents the size of the input, so O(n) means that the algorithm's time complexity will grow linearly with the size of the input.

Apart from Big-O notation, there are other notations that are used to describe the complexity of an algorithm, such as Ω (Omega) and Θ (Theta). Ω describes the best-case complexity of an algorithm, while Θ describes the average-case complexity of an algorithm.

Different data structures have different time complexities for the same operations. For example, a linked list has O(1) time complexity for insert and delete operations, while an array has O(n) time complexity for the same operations. Below you can find average and worst time complexities for data structures used commonly in web development.

Data StructureAccessSearchInsertionDeletion
Linked ListΘ(n)Θ(n)Θ(1)Θ(1)
Doubly Linked ListΘ(n)Θ(n)Θ(1)Θ(1)
Skip ListΘ(log n)Θ(log n)Θ(log n)Θ(log n)
Hash TableN/AΘ(1)Θ(1)Θ(1)
Binary Search TreeΘ(log n)Θ(log n)Θ(log n)Θ(log n)
Data StructureAccessSearchInsertionDeletion
Linked ListO(n)O(n)O(1)O(1)
Doubly Linked ListO(n)O(n)O(1)O(1)
Skip ListO(n)O(n)O(n)O(n)
Hash TableN/AO(n)O(n)O(n)
Binary Search TreeO(n)O(n)O(n)O(n)

Similar to data structures, different array sorting algorithms have different time complexities. Below you can find the best, average and worst time complexities for the most common array sorting algorithms.

Quick sortΩ(n log n)Θ(n log n)O(n^2)
Merge sortΩ(n log n)Θ(n log n)O(n log n)
Heap sortΩ(n log n)Θ(n log n)O(n log n)
Bubble sortΩ(n)Θ(n^2)O(n^2)
Insertion sortΩ(n)Θ(n^2)O(n^2)
Selection sortΩ(n^2)Θ(n^2)O(n^2)
Bucket sortΩ(n+k)Θ(n+k)O(n^2)

Written by Angelos Chalaris

I'm Angelos Chalaris, a JavaScript software engineer, based in Athens, Greece. The best snippets from my coding adventures are published here to help others learn to code.

If you want to keep in touch, follow me on GitHub.

More like this

  • JavaScript Performance Optimization

    Optimize your JavaScript with this collections of tips and tricks and take your website to the next level.

    Collection · 10 snippets

  • Asynchronous JavaScript Cheat Sheet

    Learn everything you need to know about promises and asynchronous JavaScript with this handy cheatsheet.

    JavaScript, Function · Jun 12, 2021

  • JavaScript modules Cheat Sheet

    Learn everything you need to know about JavaScript modules with this handy cheatsheet.

    JavaScript, Cheatsheet · Jun 12, 2021

  • K-means clustering

    Groups the given data into k clusters, using the k-means clustering algorithm.

    JavaScript, Algorithm · Dec 29, 2020