Cheat Sheet
Big-O & Data Structures
Complexity tables you can scan in a minute: data structures, sorting, graph algorithms and the Java collections, with the JDK facts checked against the JDK 21 source.
8
Groups
JDK 21
Facts checked
1
Diagram
01
Chapter 1 - Growth rates
The Shapes That Matter
Big-O describes how the number of steps grows with input size n, ignoring constants. It tells you what happens when the data gets 10 times bigger, not which code is faster today.
Growth rates for n = 1 to 20 (operations, cut off at 400)
| Class | Name | Typical example | Doubling n does what |
|---|---|---|---|
| O(1) | Constant | Array index, hash lookup (average) | Nothing |
| O(log n) | Logarithmic | Binary search, balanced tree lookup | Adds one step |
| O(n) | Linear | Scan an array | Doubles the work |
| O(n log n) | Linearithmic | Merge sort, heap sort, sorting in general | A little more than doubles |
| O(n^2) | Quadratic | Nested loops, insertion sort | Four times the work |
| O(n^3) | Cubic | Naive matrix multiply, Floyd-Warshall | Eight times the work |
| O(2^n) | Exponential | Subsets, naive recursive Fibonacci | Squares the work |
| O(n!) | Factorial | All permutations | Unusable beyond a dozen items |
Reading the notation
O is an upper bound (usually the worst case, unless the table says average). Omega is a lower bound and Theta is both. In interviews "O" normally means "the tight worst case unless I say otherwise".
02
Chapter 2 - Data structures
Complexity of Core Data Structures
Average case unless a column says worst. "Amortised" means averaged over a sequence of operations.
| Structure | Access by index/key | Search | Insert | Delete | Space | Gotcha |
|---|---|---|---|---|---|---|
| Array (fixed) | O(1) | O(n) | O(n) shift | O(n) shift | O(n) | Fixed size; insert in the middle moves everything |
Dynamic array (ArrayList) | O(1) | O(n) | O(1) amortised at end; O(n) elsewhere | O(n) except last | O(n) | A resize copies the whole array, but rarely |
| Singly linked list | O(n) | O(n) | O(1) at head (or at a known node) | O(1) at head; O(n) to find a node | O(n) | Poor cache locality; no backwards walk |
Doubly linked list (LinkedList) | O(n) | O(n) | O(1) at either end | O(1) at either end or at a held node | O(n) | Index access walks from the nearer end |
| Stack / queue / deque (array based) | n/a | O(n) | O(1) amortised at the ends | O(1) at the ends | O(n) | ArrayDeque beats LinkedList for both |
| Hash table | O(1) average | O(1) average | O(1) average | O(1) average | O(n) | Worst case O(n) with many collisions; resizing is O(n) |
| Binary search tree (unbalanced) | n/a | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(n) | Sorted insertion degrades it to a linked list |
| Balanced BST (AVL, red-black) | n/a | O(log n) | O(log n) | O(log n) | O(n) | Ordered iteration, range queries, floor and ceiling |
| B-tree / B+ tree | n/a | O(log n) | O(log n) | O(log n) | O(n) | Wide nodes: few disk reads; database indexes |
| Binary heap | Min or max: O(1) | O(n) | O(log n) | Remove top: O(log n) | O(n) | Building from n items is O(n); not sorted |
| Trie | n/a | O(L), L = key length | O(L) | O(L) | O(total characters) | Independent of the number of keys; memory hungry |
| Skip list | n/a | O(log n) expected | O(log n) expected | O(log n) expected | O(n) | Randomised; used in sorted sets of some stores |
| Union-Find (with path compression and union by rank) | n/a | find: near O(1) (inverse Ackermann, amortised) | union: same | n/a | O(n) | Connected components, Kruskal |
| Segment tree | n/a | Range query O(log n) | Point update O(log n) | n/a | O(n) | Build O(n) |
| Fenwick tree (BIT) | n/a | Prefix sum O(log n) | Update O(log n) | n/a | O(n) | Smaller and simpler than a segment tree for prefix sums |
| Bloom filter | n/a | O(k) hashes | O(k) | Not supported | Fixed bits | False positives, never false negatives |
| Graph: adjacency list | n/a | Edge check O(degree) | Add edge O(1) | O(degree) | O(V + E) | Best for sparse graphs |
| Graph: adjacency matrix | Edge check O(1) | n/a | O(1) | O(1) | O(V^2) | Best for dense graphs |
03
Chapter 3 - Sorting
Sorting Algorithms
The facts to memorise: which are n log n, which use extra memory, which are stable (equal items keep their order).
| Algorithm | Best | Average | Worst | Space | Stable | Note |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) with early exit | O(n^2) | O(n^2) | O(1) | Yes | Teaching only |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Fewest swaps (at most n-1) |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Great on small or nearly sorted input |
| Shell sort | O(n log n) | Depends on gaps | Depends on gaps | O(1) | No | Insertion sort with shrinking gaps |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) for arrays | Yes | Predictable; good for linked lists and external sorting |
| Quick sort | O(n log n) | O(n log n) | O(n^2) | O(log n) stack | No | Bad pivots cause the worst case; randomise or use median of three |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In place with guaranteed bound, slower in practice (cache) |
| Tim sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Merge + insertion; exploits existing runs |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes (typical version) | Integers in a small range k; not comparison based |
| Radix sort | O(d (n + k)) | O(d (n + k)) | O(d (n + k)) | O(n + k) | Yes | d digits, base k; fixed-width keys |
| Bucket sort | O(n + k) | O(n + k) for uniform data | O(n^2) | O(n + k) | Depends on the inner sort | Needs evenly distributed input |
04
Chapter 4 - Java sort facts
What the JDK Actually Does
Checked against the JDK 21 src.zip Javadoc of Arrays and List.
| Fact | Value |
|---|---|
| Lower bound for comparison sorting | Omega(n log n): no comparison sort can beat it in the worst case |
| Binary search needs | Sorted input; O(log n) steps; mid = lo + (hi - lo) / 2 avoids integer overflow |
Arrays.sort(int[]) and other primitive arrays (JDK 21 Javadoc) | Dual-Pivot Quicksort, documented as O(n log n) performance on all data sets |
Arrays.sort(Object[]), Collections.sort, List.sort | Stable merge-based sort (the List.sort Javadoc calls it stable, adaptive and iterative); needs a consistent comparator |
05
Chapter 5 - Graph and search algorithms
Algorithms You Will Be Asked About
V = vertices, E = edges.
| Algorithm | Time | Space | Use | Gotcha |
|---|---|---|---|---|
| Linear search | O(n) | O(1) | Unsorted data | Fine for small n |
| Binary search | O(log n) | O(1) | Sorted array, or "first true" on a monotone condition | Off-by-one on bounds; overflow of lo + hi |
| BFS | O(V + E) | O(V) | Shortest path in unweighted graphs, levels | Mark visited when enqueuing |
| DFS | O(V + E) | O(V) recursion or stack | Connectivity, cycles, topological order | Deep recursion can overflow the stack |
| Topological sort (Kahn or DFS) | O(V + E) | O(V) | Dependency order in a DAG | Fails (no order) if there is a cycle |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | Shortest paths, non-negative weights | Wrong with negative edges |
| Bellman-Ford | O(V E) | O(V) | Negative edges, negative cycle detection | Slow on big graphs |
| Floyd-Warshall | O(V^3) | O(V^2) | All pairs shortest paths | Only for small V |
| Kruskal (MST) | O(E log E) | O(V) | Minimum spanning tree with union-find | Sort edges first |
| Prim (MST, heap) | O(E log V) | O(V) | Minimum spanning tree | Dense graphs may prefer the matrix version |
| Dynamic programming (table) | States x transitions | States (often reducible) | Overlapping subproblems | State count drives the cost |
| Backtracking | Exponential in general | O(depth) | Subsets, permutations, constraint search | Prune early |
06
Chapter 6 - Java collections
Java Collections Complexity
What the JDK documents and the constants in the JDK 21 source (HashMap constants and ArrayList growth read from src.zip).
| Collection | get / contains | add / put | remove | Ordered? | Gotcha |
|---|---|---|---|---|---|
ArrayList | get(i) O(1); contains O(n) | add at end O(1) amortised; add(i, x) O(n) | remove(i) O(n); last element O(1) | Insertion order | Grows by about 1.5 times (preferred growth is half the old capacity) |
LinkedList | get(i) O(n); contains O(n) | add first or last O(1) | ends O(1); by index or value O(n) | Insertion order | Index operations traverse from the nearer end; usually slower than ArrayList in practice |
ArrayDeque | contains O(n) | addFirst, addLast O(1) amortised | pollFirst, pollLast O(1); remove(Object) O(n) | Insertion order | No null elements; faster than Stack and LinkedList as a stack or queue |
HashMap / HashSet | O(1) average | O(1) average | O(1) average | No | Default capacity 16, load factor 0.75; resize doubles and rehashes |
HashMap with colliding keys | O(log n) in a treeified bin | same | same | No | A bin turns into a tree when it reaches 8 nodes and the table has at least 64 buckets; otherwise the table is resized instead. It turns back to a list at 6 or fewer |
LinkedHashMap | O(1) | O(1) | O(1) | Insertion or access order | Access order mode gives an LRU cache with removeEldestEntry |
TreeMap / TreeSet | O(log n) | O(log n) | O(log n) | Sorted by key | Javadoc: guaranteed log(n) for containsKey, get, put and remove; no null keys with natural ordering |
PriorityQueue | peek O(1); contains O(n) | offer O(log n) | poll O(log n); remove(Object) O(n) | Heap order, not sorted | Iterating does not give sorted order |
ConcurrentHashMap | O(1) average | O(1) average | O(1) average | No | Lock-free reads; compound check-then-act still needs computeIfAbsent or similar |
CopyOnWriteArrayList | O(1) | O(n) (copies the array) | O(n) | Insertion order | For read-mostly lists only |
Collections.sort / List.sort | n/a | O(n log n) | n/a | n/a | Stable; sorts an array copy then writes back (default List.sort) |
String.concat in a loop | n/a | O(n^2) overall | n/a | n/a | Use StringBuilder for O(n) |
List.contains in a loop | n/a | O(n*m) | n/a | n/a | Put one side in a HashSet |
07
Chapter 7 - Limits and amortisation
Rules of Thumb and Amortisation
Use input limits in a problem statement to pick the target complexity. The thresholds below are planning heuristics, not measurements; real speed depends on language, memory access and hardware, and ~10^8 simple operations per second is only an order-of-magnitude guess.
| If n is up to | You can afford about | Typical algorithms |
|---|---|---|
| 10 to 11 | O(n!) | All permutations |
| 20 to 25 | O(2^n) | Subsets, bitmask DP |
| around 100 to 500 | O(n^3) | Floyd-Warshall, triple loops |
| around 5,000 to 10,000 | O(n^2) | Nested loops, simple DP tables |
| around 10^5 to 10^6 | O(n log n) | Sorting, heaps, balanced trees, sweep lines |
| around 10^7 to 10^8 | O(n) | One or a few passes, hashing |
| above that | O(log n) or O(1) | Binary search, math formulas, precomputation |
| Amortised idea | Explanation |
|---|---|
| Dynamic array append | Most appends cost 1 step; a resize copies n items. Growth by a constant factor keeps the average per append constant: adding n elements costs O(n) in total (stated in the ArrayList Javadoc) |
| Growing by a fixed amount instead | Adding a fixed number of slots each time makes n appends cost O(n^2) in total |
| Hash table resize | Rehash is O(n) but happens after n/2 more inserts, so inserts stay O(1) on average |
| Counting trick | Each element is moved to a stack or queue at most a constant number of times, so total work is O(n) even with a nested loop (monotonic stack, sliding window, two pointers) |
08
Chapter 8 - Common mistakes
Complexity Mistakes
⚠ The ones that cost real time
- Calling hash map operations O(1) without the caveat. It is O(1) on average with a good hash; worst case degrades (Java treeifies a long bin so it is O(log n) there).
- Forgetting hidden costs.
list.remove(0),String +=in a loop,list.containsinside a loop andsubstringcopies are all O(n). - Counting only loops. Recursion depth, sorting inside a loop and library calls count too.
- Dropping a variable. BFS is O(V + E), not O(n). Two inputs need two variables.
- Ignoring space. Merge sort is O(n) extra, recursion uses stack space, memoisation uses a table.
- Confusing amortised with average. Amortised is a guarantee over a sequence; average is over random inputs.
- Optimising constants first. Fix the algorithm class, then measure.
- **Treating
LinkedListas faster for inserts.** Finding the position costs O(n) and cache misses make it slower thanArrayListin most real programs.
09
Chapter 9 - Go deeper
Long-form pages and what was checked
| Topic | Page |
|---|---|
| Complexity analysis explained | Complexity |
| Arrays and dynamic arrays | Array |
| Linked lists, stacks, queues, deques | Linked List, Stack, Queue, Deque |
| Hash maps and sets | Hash Map, Hash Set |
| Trees, heaps, tries | Binary Tree, BST, Heap, Trie |
| Graph algorithms | Graph Basics, BFS, DFS, Shortest Path |
| Sorting | Sorting |
| Java collections | Java Collections Framework |
| DSA index | Data Structures & Algorithms |
Version note
Checked on 2026-10-31 against JDK 21 (21.0.2) src.zip: HashMap constants (default capacity 16, load factor 0.75, treeify threshold 8, untreeify threshold 6, minimum treeify capacity 64 and the "resize instead of treeify" comment), ArrayList growth (preferred growth of half the old capacity, so about 1.5 times) and its amortised-constant statement, TreeMap log(n) guarantee, PriorityQueue log(n) enqueue/dequeue and linear remove(Object)/contains notes, ArrayDeque amortised-constant and linear-exception notes, Arrays dual-pivot quicksort for primitives, and the List.sort stable-sort wording. The textbook complexities of data structures, sorting and graph algorithms are standard results listed from knowledge, not re-fetched from a source for this sheet; the n-limit table is a heuristic and is labelled as such. The inverse-Ackermann bound for union-find assumes both path compression and union by rank.