Big O Cheat Sheet — Data Structures, Algorithms, and Language Gotchas
A canonical Big-O cheat sheet for coding interview prep — data structure operations, sorting and graph algorithm complexities, and per-language notes for Python, Java, and JavaScript that generic cheat sheets leave out.
Bookmark this page. It's the reference: complexities you should know cold for coding interviews, plus the language-specific gotchas (Python x in list, Java LinkedList.get, JS Array.shift) that generic Big-O tables usually leave out. Screenshot the tables, skim the gotchas, come back when you need to argue an amortised bound in front of an interviewer.
Data structure operations
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Contiguous, fixed size |
| Dynamic array | O(1) | O(n) | O(1)* at end / O(n) mid | O(n) | *Amortised over resizes |
| Sorted array | O(1) | O(log n) | O(n) | O(n) | Binary-searchable |
| Linked list | O(n) | O(n) | O(1)† | O(1)† | †Given a node pointer |
| Doubly linked list | O(n) | O(n) | O(1)† | O(1)† | O(1) both directions |
| Stack | — | O(n) | O(1) | O(1) | LIFO |
| Queue | — | O(n) | O(1) | O(1) | FIFO |
| Deque | O(1) ends | O(n) | O(1) ends | O(1) ends | Double-ended |
| Hash map | — | O(1)‡ | O(1)‡ | O(1)‡ | ‡Amortised; worst O(n) on collisions |
| Hash set | — | O(1)‡ | O(1)‡ | O(1)‡ | Same |
| Binary heap | O(1) peek | O(n) | O(log n) | O(log n) | Root only for peek |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | Red-black, AVL |
| Trie | — | O(k) | O(k) | O(k) | k = key length |
Sorting algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | O(1) | ✓ |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ✗ |
| Bubble | O(n) | O(n²) | O(n²) | O(1) | ✓ |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | ✓ |
| Radix | O(n · k) | O(n · k) | O(n · k) | O(n + k) | ✓ |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | ✓ |
Graph algorithms
| Algorithm | Time | Space |
|---|---|---|
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(V) |
| Dijkstra (min-heap) | O((V + E) log V) | O(V) |
| Bellman-Ford | O(V · E) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
| Kruskal (with union-find) | O(E log E) | O(V) |
| Prim (with min-heap) | O((V + E) log V) | O(V) |
| Topological sort | O(V + E) | O(V) |
| A* (admissible heuristic) | O((V + E) log V) | O(V) |
String algorithms
| Task | Time | Space |
|---|---|---|
| Naive substring search | O(n · m) | O(1) |
| KMP substring search | O(n + m) | O(m) |
| Rabin-Karp (rolling hash) | O(n + m) average | O(1) |
| Longest common subsequence | O(n · m) | O(n · m) |
| Edit distance (Levenshtein) | O(n · m) | O(n · m) |
| Longest palindromic substring (expand-around-centre) | O(n²) | O(1) |
| Manacher's algorithm | O(n) | O(n) |
Specialised structures
| Structure | Operation | Complexity | Notes |
|---|---|---|---|
| Union-Find (path compression + union by rank) | union / find | O(α(n)) ≈ O(1) | Inverse Ackermann — treat as constant |
| Segment tree | query / update | O(log n) | O(n) build, O(n) space |
| Fenwick tree (BIT) | update / prefix sum | O(log n) | O(n) space |
| LRU cache (hashmap + DLL) | get / put | O(1) | Interview-classic composition |
| Bloom filter | insert / contains | O(k) | k = number of hash functions; false positives possible |
Common interview algorithms
| Task | Time | Space |
|---|---|---|
| Two-sum (hash map) | O(n) | O(n) |
| Binary search | O(log n) | O(1) |
| Merge two sorted lists | O(n + m) | O(1) |
| Reverse linked list | O(n) | O(1) |
| Detect cycle (Floyd's tortoise/hare) | O(n) | O(1) |
| Longest substring without repeats (sliding window) | O(n) | O(k) |
| Trapping rain water (two-pointer) | O(n) | O(1) |
| Median of two sorted arrays (binary search) | O(log(min(n, m))) | O(1) |
| N-queens (with pruning) | ≈O(n!) worst | O(n) |
| Subsets | O(n · 2ⁿ) | O(n · 2ⁿ) |
| Permutations | O(n · n!) | O(n · n!) |
| Fibonacci (naive recursion) | O(2ⁿ) | O(n) |
| Fibonacci (DP) | O(n) | O(1) |
| Coin change (DP) | O(n · amount) | O(amount) |
How to read these tables
Three ideas fill in the gaps every generic Big-O reference glosses over.
Amortised means averaged over a sequence of operations, not per-op worst case. list.append in Python is amortised O(1) — occasionally an operation triggers a resize costing O(n), but averaged over any long sequence you pay O(1) per call. Interviewers accept "amortised O(1)" as the answer for hash-map ops and dynamic-array appends; if you say O(1) without qualification and get pressed, you should be ready to defend or downgrade.
Worst-case is the pathological scenario, not the typical one. Quicksort is O(n log n) average but O(n²) if you pick pivots poorly on an already-sorted array. Java's HashMap degrades from O(1) to O(log n) inside a bucket that fills with collisions (post-Java-8 the bucket becomes a red-black tree). Naming the worst case is what separates a memorised answer from an understood one.
k is a scale variable that isn't n. In tries and radix sort, k is the key length. In counting sort, k is the number of distinct values. When k is small and bounded — ASCII strings, bytes, days-of-the-week — these algorithms beat comparison sorts. When k is unbounded or grows with n, they don't.
Python-specific gotchas
dict[k],dict.get(k),k in dict,del dict[k]: amortised O(1). Worst case O(n) on a resize or an adversarial collision; rare in practice.list.append(x),list.pop()(from the end): amortised O(1).list.pop(0),list.pop(mid),list.insert(i, x)fori != len(list): O(n). If you need O(1) at both ends, reach forcollections.deque.x in list: O(n). The classic interview slowdown. Convert tosetif you'll do more than one lookup.list.sort(),sorted(iterable): O(n log n) — Timsort. Stable.set.add,set.remove,x in set: amortised O(1).collections.deque: O(1)append/pop/appendleft/popleft.heapq.heappush(h, x),heapq.heappop(h): O(log n).heapq.heapify(list)is O(n) — not O(n log n), thanks to the bottom-up construction.str + strin a loop: O(n²) — strings are immutable, every concat allocates a new string. Collect pieces into a list and use''.join(pieces)for O(total_length).str[a:b]: O(b − a) — slicing creates a new string.str.find,str.startswith,str.endswith: O(n).Counter(iterable): O(n) to build.Counter.most_common(k)uses a heap: O(n log k).sorted(dict.items(), key=lambda kv: kv[1]): O(n log n) and returns a fresh list.
Java-specific gotchas
HashMap.get / put / remove / containsKey: amortised O(1). Post-Java-8, worst case per bucket is O(log n) via a red-black tree fallback on high-collision buckets.ArrayList.get / set: O(1).add(x)at end: amortised O(1).add(i, x)orremove(i)forimid-list: O(n).contains(x): O(n).LinkedList.get(i): O(n) — walks the list. Almost always useArrayListin interview code;LinkedListonly earns its keep for O(1) both-ends inserts, and even thenArrayDequeis faster in practice.HashSet.add / contains / remove: amortised O(1).TreeMap/TreeSet: O(log n) for all ops. Iteration in sorted order for free.PriorityQueue: O(log n) foradd/poll; O(1) forpeek. Min-heap by default; pass aComparator.reverseOrder()for a max-heap.ArrayDeque: O(1)push/pop/peek. Prefer over the legacyStack(synchronised, slow) andLinkedList(poor cache locality).StringBuilder.append: amortised O(1). Never dostr += ...onStringin a loop — the immutable-Stringconcat is O(n²).Arrays.sort(int[]): dual-pivot Quicksort — O(n log n) average, O(n²) worst case.Arrays.sort(Object[]),Collections.sort(List): Timsort — O(n log n) worst case. Stable.String.substring(a, b): O(b − a) post-Java-7 (it now copies rather than sharing the backing array).
JavaScript-specific gotchas
Map.get / set / has / delete: O(1) per spec (V8 uses hash tables).Object[k]: nominally O(1), but subject to polymorphic-inline-cache regressions when the property set becomes heterogeneous. For hot inner loops, preferMap.Array.push,Array.pop: amortised O(1).Array.shift,Array.unshift: O(n) — every element shifts. This is the accidental-O(n²) trap when using an array as a queue; use a head-index counter, or push new items and reverse-iterate.Array.splice(i, count, ...items): O(n).Array.includes,Array.indexOf,Array.find: O(n). Convert toSetfor repeated membership tests.Array.sort: implementation-defined but stable per ES2019 spec; V8 uses TimSort — O(n log n).Set.add / has / delete: O(1).- String concatenation with
+: modern engines use rope structures, soa + bis often O(1), but the patterns = s + tinside a loop can still degrade. For guaranteed O(n), collect pieces into an array and callarr.join(''). JSON.parse,JSON.stringify: O(size of the serialised form), not to be assumed as O(1) even for "small" objects.
Space complexity essentials
Space complexity counts memory beyond the input. Interviewers occasionally let you count the input array as O(n) if you're modifying it in place; if it matters, ask.
- Iterative algorithms using O(1) auxiliary variables (two-pointer scans, Floyd's cycle detection, in-place reverses): O(1) space.
- Recursive algorithms: at least O(depth) for the call stack. DFS on a balanced tree is O(log n); on a skewed one it's O(n) and can stack-overflow. Convert to iterative if depth is a concern.
- DP memoisation table: O(states) — usually O(n), O(n · m), or O(2ⁿ · n) depending on state definition.
- BFS queue: worst-case width of the tree or graph. For graphs, O(V). For perfectly balanced trees at depth d, O(2ᵈ) — the widest level dominates.
- Backtracking result list: O(count × solution size). Don't forget to include the size of what you're recording, not just the count.
How to argue Big-O in an interview
Interviewers grade the argument, not the answer. Answering "O(n)" without a walk-through looks like a memorised guess; walking through the argument shows the skill they're actually screening for. Three lines you can say out loud:
- Name the input size symbols. "Let n be the length of
nums, m the length oftarget." - Break the algorithm into named work. "The outer loop runs n times. Each iteration does a hash-map insert (amortised O(1)) and a scan of
current(O(k), where k is the current window length, bounded by n)." - Sum, drop constants, drop dominated terms. "So the total is O(n × k), which in the worst case is O(n²). Space is O(n) for the map."
If the interviewer pushes back, defend the amortised claim ("hash-map insert averages O(1) even though a bad collision could be O(n)"), or downgrade cleanly ("if I can't assume good hashing, the worst-case bound is O(n²) for the whole loop"). Either move earns credit; hedging without commitment loses it.
The patterns this table backs
Every pattern in the interview-prep tier reduces to something on the tables above. The tables aren't wallpaper — they're what a technique is buying you.
- The sliding-window pattern hinges on hash map and set operations being O(1) — that's what makes the "extend right, shrink left" scan O(n) instead of O(n · k).
- The two-pointer pattern is O(n) after an optional O(n log n) sort; the sort is why 3Sum is O(n²) instead of O(n³) and why LC 15's dedup step exists.
- The binary-search template is O(log n) on any monotone-predicate space. The "binary search on answer" variant converts an O(m) linear scan of an answer domain into O(log m × cost-of-predicate) — that's the LC 1011 collapse.
- The monotonic stack pattern is O(n) because each element is pushed once and popped at most once — the amortised-O(1)-per-element argument straight from the dynamic-array-append line.
- The backtracking template inherits O(n · n!) for permutations and O(n · 2ⁿ) for subsets from the common-algorithms table; the technique's job is to make the pruned tree hit those bounds only in the worst case.
If you can walk into a whiteboard, name which line of the tables above your algorithm cashes in on, and defend the amortised claim, the Big-O question is already answered. That's the interview reflex the whole series is aimed at.