Cheat sheet · Computer science
Big-O and data structures cheat sheet
Growth rates, the cost of common operations, sorting algorithms and the patterns behind interview questions.
- Sections
- 5
- Items
- 32
- Area
- Computer science
- Download
- PNG, PDF
Cheat sheet
Big-O and data structures
Growth rates, the cost of common operations, sorting algorithms and the patterns behind interview questions.
Growth rates (best to worst)
O(1)- Constant: same time for any size
O(log n)- Halves the work each step (binary search)
O(n)- One pass over the data
O(n log n)- Good sorting
O(n²)- A loop inside a loop
O(2ⁿ) / O(n!)- Tries every subset / every order. Only for tiny inputs
Cost of operations
Array: read by index- O(1)
Array: insert or delete in the middle- O(n)
Linked list: insert at a known node- O(1)
Hash map: get, set, delete- O(1) on average
Stack / queue: push, pop, enqueue, dequeue- O(1)
Balanced search tree: find, insert- O(log n)
Heap: insert, remove smallest- O(log n)
Heap: see the smallest- O(1)
Sorting
Merge sort- O(n log n) always; needs extra space; stable
Quick sort- O(n log n) on average, O(n²) worst; in place
Heap sort- O(n log n); in place; not stable
Insertion sort- O(n²); fast on nearly sorted small data
Counting sort- O(n + k) when values are small whole numbers
Patterns
Two pointers- Two positions move through sorted data or from both ends
Sliding window- A range that grows and shrinks over an array or string
Binary search- Halve a sorted range, or a yes/no answer, each step
Hash map for counting- Count, group or look up in one pass
BFS / DFS- Breadth first (queue, shortest steps) / depth first (stack or recursion)
Dynamic programming- Break into overlapping smaller problems and remember the answers
Backtracking- Build choices step by step and undo when stuck
Heap for top k- Keep the k best items while scanning
How to solve a question
1. Restate- Say the problem and ask about edge cases
2. Example- Work a small input by hand
3. Simple first- State the slow way, then improve it
4. Code- Write clean code and name variables clearly
5. Test- Walk through the example and an edge case
Remember
- Say the time and space cost of your answer before the interviewer asks.
- With 1,000 items, n² is 1 million steps. With 100,000 items it is 10 billion. Check the input size first.
Learn it properly
A cheat sheet helps you remember. These lessons explain the ideas step by step, with examples.