Big O Cheat Sheet

thebigobook.com — Robert M. Cavezza

Common Big O Growth Patterns

Notation	Nickname	What it means	Example
O(1)	The Vending Machine	Work stays the same as the input grows	Array index; expected Map/Set lookup
O(log n)	The Halving	Cuts the remaining work in half each step	Binary search
O(n)	The Roll Call	One full pass through the input	Loop, find, filter, linear search
O(n x m)	The Two Crowds	Each item in one list checks the other list	.find() or .includes() inside a loop
O(n log n)	The Sorting Tax	Efficient general comparison sorting	Merge sort; typically Array.sort()
O(n²)	The Handshake Problem	Every item meets every other item	Same-size nested loops; bubble sort
O(n³)	The Triple Loop	Three full-size dimensions multiply	Three same-range nested loops
O(2ⁿ)	The Doubling Monster	Each extra choice can double the cases	Naive Fibonacci; all subsets
O(n!)	The Seating Chart Nightmare	Tries every possible ordering	Generating all permutations

JavaScript Built-in Costs

Array

arr[i]O(1)

.push() / .pop()usually O(1)

.shift() / .unshift()O(n)

.includes() / .indexOf()O(n)

.find() / .findIndex()O(n)

.map() / .filter() / .forEach()O(n)

.slice() / .concat()O(n)

.splice() (middle)O(n)

.sort()typically O(n log n)

Map / Set / JSON

map.get() / map.set()expected O(1)

set.has() / set.add()expected O(1)

JSON.parse() / stringify()O(n)

These are typical costs for ordinary arrays, Maps, and Sets; exact engine behavior can vary. sort() changes its array.

Container Picker

Array Ordered list. Get by position: O(1). Search: O(n). Add or remove at the front: O(n).

Object/Map Look up by name or ID. Get, add, or remove by key: usually O(1).

Set Unique values or seen-before checks. Check, add, or remove: usually O(1).

Stack Undo or last in, first out. Add or remove the top item: usually O(1).

Queue Process in arrival order. Use a proper queue or head pointer; do not repeatedly shift a large array.

Tree/Graph Use for hierarchies or relationships.

Slow-Code Checklist

Five Practical Fixes

01 Map instead of find-in-loop. Build a keyed lookup once, then use expected near-constant-time access.
02 Set for seen-before checks. Replace repeated membership scans with expected near-constant-time membership.
03 Sort once. If the data and comparator stay unchanged, pay the sorting cost once and reuse the result.
04 Don't touch the front repeatedly. Use a head pointer or proper queue instead of shifting an array.
05 Stop at enough. Stop after the next chunk, a specific match, or the first 50 items. Worst-case Big O may stay O(n), while actual work falls.

Rule of pocket: Some of the biggest speed gains come from avoiding work the result never needs.