Big O Cheat Sheet: Time Complexity Chart with JavaScript

Short answer: Big O notation describes how the work an algorithm does grows as the input grows. From best to worst: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2ⁿ) exponential and O(n!) factorial.

Below: what each one looks like in JavaScript, a chart of how fast they grow, what common array, Map and Set operations cost, and a table of sorting and searching algorithms.

How to read Big O

  • n is the size of the input, like the length of an array.
  • It describes growth, not speed. O(n) means doubling the input roughly doubles the work. It says nothing about how many milliseconds one step takes.
  • Constants and smaller terms are dropped. 2n + 10 is O(n). n² + n is O(n²).
  • It usually means the worst case unless someone says “average” or “amortized”.
  • Space complexity uses the same notation for extra memory instead of time.

Big O complexity chart

Approximate number of steps for each complexity as n grows (log is base 2, rounded):

Complexity Name n = 10 n = 100 n = 1,000 n = 1,000,000
O(1) Constant 1 1 1 1
O(log n) Logarithmic 3 7 10 20
O(n) Linear 10 100 1,000 1,000,000
O(n log n) Linearithmic 33 664 ~10,000 ~20,000,000
O(n²) Quadratic 100 10,000 1,000,000 10¹²
O(2ⁿ) Exponential 1,024 ~10³⁰ too many too many
O(n!) Factorial 3,628,800 too many too many too many

The jump from O(n) to O(n²) is where most real-world slowness comes from: fine with 100 items, painful with 100,000.

O(1): constant time

The work doesn’t depend on the input size. Reading an array item by index, or a Map lookup (on average).

function first(items) {
  return items[0];
}

O(log n): logarithmic time

Each step cuts the remaining work in half. Binary search on a sorted array finds an item among a million in about 20 steps.

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

binarySearch([1, 3, 5, 7, 9, 11], 7); // 3

O(n): linear time

One pass over the input. Most array methods that look at every item, like map, filter, reduce and includes, are linear.

function sum(numbers) {
  let total = 0;
  for (const n of numbers) total += n;
  return total;
}

O(n log n): linearithmic time

The cost of efficient comparison sorting. When you call sort(), assume O(n log n).

const sorted = [5, 1, 4].sort((a, b) => a - b); // [1, 4, 5]

O(n²): quadratic time

A loop inside a loop over the same data. This duplicate check compares every pair. The Set version does the same job in O(n) on average; with 20,000 items it ran about 70 times faster in Node.

// O(n²)
function hasDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true;
    }
  }
  return false;
}

// O(n) on average
function hasDuplicateFast(items) {
  return new Set(items).size !== items.length;
}

O(2ⁿ): exponential time

Each call starts two more. Naive recursive Fibonacci is the classic example: every extra n roughly doubles the work. Caching results (memoization) or a simple loop brings it down to O(n).

function fib(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

fib(10); // 55

Time complexity of common JavaScript operations

The ECMAScript spec defines what these methods do, not how fast they are, so these are the typical costs in modern engines. One exception: the spec does require Map and Set to be implemented with “hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements”. Sublinear is a guarantee; O(1) on average is what engines deliver in practice.

Operation Typical cost
arr[i], arr.length O(1)
push(), pop() O(1) amortized
shift(), unshift() O(n) (every other item moves)
splice() in the middle O(n)
includes(), indexOf(), find() O(n)
map(), filter(), reduce(), forEach() O(n)
slice(), spread [...arr], concat() O(n) (copies)
sort() O(n log n)
Map/Set: get, set, has, add, delete O(1) on average
Object property read/write Usually O(1)

“Amortized” means an occasional push() is slow (when the engine grows the array’s storage) but the average over many pushes is constant. In a quick Node test, removing 200,000 items with shift() took over a second while pop() took under a millisecond, which is the O(n) vs O(1) difference in practice. If you need a queue, keep a head index instead of calling shift() in a loop.

The everyday win is swapping a repeated includes() for a Set: checking 10,000 items against an array of 10,000 can take up to 100 million comparisons; against a Set it is about 10,000 lookups. More on these methods in 10 JavaScript array methods and on MDN’s Map reference.

Sorting algorithms cheat sheet

Algorithm Best Average Worst Extra space Stable
Bubble sort* O(n) O(n²) O(n²) O(1) Yes
Insertion sort O(n) O(n²) O(n²) O(1) Yes
Selection sort O(n²) O(n²) O(n²) O(1) No
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quicksort O(n log n) O(n log n) O(n²) O(log n)** No
Heapsort O(n log n) O(n log n) O(n log n) O(1) No
Timsort O(n) O(n log n) O(n log n) O(n) Yes

* With the usual early exit when a pass makes no swaps. ** Stack space for typical in-place implementations.

Which one does JavaScript use? The spec doesn’t say, but since ES2019 it requires Array.prototype.sort() to be stable. V8 (Chrome, Node.js) has used Timsort since V8 7.0, as explained on the V8 blog. Note that sort() without a compare function sorts as strings: [10, 9, 1].sort() gives [1, 10, 9].

Searching algorithms

Algorithm Best Average Worst Needs
Linear search O(1) O(n) O(n) Nothing
Binary search O(1) O(log n) O(log n) Sorted array
Hash lookup (Map, Set) O(1) O(1) O(n) A hash table

The O(n) worst case for hashing happens when many keys land in the same bucket. Good implementations make that rare.

If you are preparing for interviews, these tables cover most of the complexity questions you’ll get; these technical interview resources cover the rest of the prep.

FAQ

What is Big O notation in simple terms?

A way to describe how much slower an algorithm gets as its input gets bigger. O(n) grows in step with the input, O(n²) grows with its square, O(1) doesn’t grow at all.

What is the fastest time complexity?

O(1), constant time. Next is O(log n), which grows so slowly that it behaves almost like constant time in practice.

What is the time complexity of a nested loop?

If both loops run over the same n items, O(n²). If they run over different inputs of size n and m, O(n × m).

Is Array.prototype.includes O(1)?

No. It checks items one by one, so it is O(n). For repeated lookups, build a Set once and use has(), which is O(1) on average.

Does Big O tell me which code is faster?

Only for large inputs. For small arrays, a simple O(n²) loop can beat a cleverer algorithm because constants matter. Measure when it matters.