ChoralSoft Learn
Printable cheat sheets
One page each. Choose a sheet, then print it or save it as a PDF.
Big-O and data structures
Typical costs for the structures you reach for most often. n is the number of items.
Growth rates, slowest growth first
| Class | Name | Typical example |
|---|---|---|
| O(1) | Constant | Array lookup by index, hash table lookup (average) |
| O(log n) | Logarithmic | Binary search, balanced tree lookup, heap insert |
| O(n) | Linear | Scan a list, build a heap |
| O(n log n) | Linearithmic | Merge sort, heap sort, quicksort (average) |
| O(n²) | Quadratic | Compare every pair, simple sorts |
| O(2ⁿ) | Exponential | Try every subset |
| O(n!) | Factorial | Try every ordering |
Data structure operations
| Structure | Access / search | Insert | Delete | Notes |
|---|---|---|---|---|
| Array | O(1) by index, O(n) search | O(n) in the middle, O(1) amortized at the end | O(n) | Contiguous memory, cache friendly |
| Linked list | O(n) | O(1) at a known node | O(1) at a known node | No random access |
| Hash table | O(1) average, O(n) worst | O(1) average | O(1) average | No ordering of keys |
| Stack / queue | O(n) search | O(1) push / enqueue | O(1) pop / dequeue | LIFO / FIFO |
| Binary heap | O(1) peek min or max | O(log n) | O(log n) for the root | Build from a list in O(n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | Keeps keys sorted; unbalanced worst case is O(n) |
| Trie | O(L) for a key of length L | O(L) | O(L) | Great for prefixes |
From ChoralSoft, choralsoft.com/learn/cheatsheets/. Free to print and share.