Reference

Big-O Cheat Sheet

The common time and space complexity classes, ranked from fastest to slowest, with plain-English explanations and where each one actually shows up in code.

Complexity classes at a glance

Notation	Name	When it appears
O(1)	Constant	Array index access, hash map lookups, arithmetic operations — anything that does the same fixed amount of work regardless of input size.
O(log n)	Logarithmic	Binary search, balanced binary search trees, and any algorithm that halves the problem size each step.
O(n)	Linear	A single loop over the input — array traversal, linear search, computing a sum.
O(n log n)	Linearithmic	Efficient comparison-based sorting (merge sort, heapsort, quicksort's average case), and divide-and-conquer algorithms that do O(n) work at each of O(log n) levels.
O(n²)	Quadratic	Nested loops over the same input — bubble sort, insertion sort, checking all pairs in a collection, and quicksort's worst case on unlucky pivot choices.
O(2ⁿ)	Exponential	Naive recursive solutions that branch on every element — unoptimized recursive Fibonacci, brute-force subset generation.
O(n!)	Factorial	Generating every permutation of a set, brute-force solutions to the traveling salesman problem.

O(1) — Constant

Array index access, hash map lookups, arithmetic operations — anything that does the same fixed amount of work regardless of input size.

const first = array[0];

O(log n) — Logarithmic

Binary search, balanced binary search trees, and any algorithm that halves the problem size each step.

while (low <= high) { mid = (low+high)/2; ... }

Binary Search — worked example →

O(n) — Linear

A single loop over the input — array traversal, linear search, computing a sum.

for (const x of array) { sum += x; }

O(n log n) — Linearithmic

Efficient comparison-based sorting (merge sort, heapsort, quicksort's average case), and divide-and-conquer algorithms that do O(n) work at each of O(log n) levels.

array.sort(); // typical O(n log n) implementation

Merge Sort — worked example →

O(n²) — Quadratic

Nested loops over the same input — bubble sort, insertion sort, checking all pairs in a collection, and quicksort's worst case on unlucky pivot choices.

for (i of a) { for (j of a) { compare(i, j); } }

Quicksort — how it degrades to O(n²) →

O(2ⁿ) — Exponential

Naive recursive solutions that branch on every element — unoptimized recursive Fibonacci, brute-force subset generation.

fib(n) = fib(n-1) + fib(n-2) // no memoization

O(n!) — Factorial

Generating every permutation of a set, brute-force solutions to the traveling salesman problem.

permutations(array) // all n! orderings

Growth rate, roughly ordered

From fastest-growing input handling to slowest, for an input of size n:

O(1) — constant
O(log n) — logarithmic
O(n) — linear
O(n log n) — linearithmic
O(n²) — quadratic
O(2ⁿ) — exponential
O(n!) — factorial

As n grows, the gap between these classes widens dramatically — an O(n²) algorithm on 10,000 items does 100 million operations, while an O(n log n) algorithm does roughly 130,000.

Next steps

If you want the reasoning behind these classifications — how to actually look at a loop or a recursive function and derive its Big-O — read the full guide:

How to Analyze Time Complexity of Any Algorithm →

This table covers time complexity — memory usage is analyzed the same way. See Space Complexity Explained →