Cheat sheet
Big-O master table
1<log n<n<n log n<n²<n³<2ⁿ<n!
Sorting
| Sort | Best | Average | Worst | Extra space | Stable | In-place |
|---|---|---|---|---|---|---|
| Selection | O(n²) | O(n²) | O(n²) | O(1) | no | yes |
| Bubble (with flag) | O(n) | O(n²) | O(n²) | O(1) | yes | yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | yes | yes |
| Shell (n/2 gaps) | O(n log n) | O(≈ n^1.5) | O(n²) | O(1) | no | yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes | no |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | no | yes |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | no | yes |
Data structure operations
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Sorted array | O(1) | O(log n) | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) at head | O(1) at head |
| Doubly linked list | O(n) | O(n) | O(1) at either end | O(1) given the node |
| Stack | – | – | O(1) push | O(1) pop |
| Queue (circular / list) | – | – | O(1) enqueue | O(1) dequeue |
| BST (balanced / skewed) | – | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) |
| Max-heap | O(1) max | O(n) | O(log n) | O(log n) max |
| Hash table (avg / worst) | – | O(1) / O(n) | O(1) / O(n) | O(1) / O(n) |
Graphs: BFS and DFS are O(V + E) with an adjacency list, O(V²) with a matrix. Matrix space O(V²), list space O(V + E).
Every topic
1.1 What Is a Data Structure?
| Array: read item i | O(1) |
| Array: insert at the front | O(n): shift everything |
| Linked list: insert at the front | O(1) |
| Linked list: read item i | O(n): walk from the head |
1.2 ADTs & Abstraction
| push / pop / top (array implementation) | O(1) |
| push / pop / top (linked implementation) | O(1) |
| Maximum size | array: fixed · linked list: limited only by memory |
1.3 Arrays & 2-D Arrays (Review)
| Access a[i] | O(1) |
| Search (unsorted) | O(n) |
| Insert / delete at position i | O(n): shift items |
| Insert / delete at the end | O(1) if there is space |
| Traverse an R × C matrix | O(R·C) |
2.1 Algorithms & Their Properties
| findMax: comparisons | exactly n − 1 |
| findMax: time | O(n), and best = worst |
2.2 Measuring Efficiency
| Search with late termination | always n checks |
| Search that breaks early | 1 … n checks |
| Duplicate check with nested loops | O(n²) time, O(1) space |
| Duplicate check with a set | O(n) time, O(n) space ← trade-off |
2.3 Counting Time Units
Single loop for(i=0;i<n;i++) k=k+1; cout<<k; | T(n) = 4n + 3 → O(n) |
Nested n × n loop with k++ | T(n) = 3n² + 4n + 3 → O(n²) |
Loop where i doubles (i *= 2) | ≈ log₂ n iterations → O(log n) |
2.4 Best, Average & Worst Case
| Linear search: best (key is first) | O(1): 1 comparison |
| Linear search: average (key present) | (n + 1) / 2 comparisons → O(n) |
| Linear search: worst (last or missing) | n comparisons → O(n) |
| Bubble sort with flag: best / worst | O(n) / O(n²) |
2.5 Asymptotic Notation & Big-O Proofs
| O(1) | constant: array access, push/pop |
| O(log n) | logarithmic: binary search |
| O(n) | linear: linear search, traversal |
| O(n log n) | linearithmic: merge sort, heap sort |
| O(n²) | quadratic: bubble, selection, insertion sort |
| O(n³) | cubic: three nested loops |
| O(2ⁿ) | exponential: all subsets, naive Fibonacci |
3.1 Selection Sort
| Best case | O(n²): it still scans for the minimum every pass |
| Average case | O(n²) |
| Worst case | O(n²): n(n−1)/2 comparisons |
| Swaps | at most n − 1 (the fewest of the simple sorts) |
3.2 Bubble Sort
| Best case (already sorted) | O(n): one pass, no swaps, stop |
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and swaps |
3.3 Insertion Sort
| Best case (already sorted) | O(n): n − 1 comparisons, 0 shifts |
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and shifts |
3.4 Pointer Sort
| Comparisons | same as the underlying sort (here selection: n(n−1)/2) |
| Data moved per swap | one pointer (8 bytes) instead of one whole record |
| Time | O(n²) with selection sort; O(n log n) with a fast sort |
3.5 Linear Search
| Best case | O(1): key at index 0 |
| Average case (found) | (n + 1)/2 comparisons → O(n) |
| Worst case | O(n): last item or not present |
| Needs sorted data? | No |
3.6 Binary Search
| Best case | O(1): key is at the first mid |
| Average / worst case | O(log n): about ⌊log₂ n⌋ + 1 comparisons |
| 1,000,000 items | at most 20 comparisons |
| Needs sorted data? | Yes, and random access (an array, not a linked list) |
3.7 Recursion Primer
| factorial(n): time | O(n): n calls, O(1) work each |
| factorial(n): space | O(n) stack frames |
| recursive binary search: time | O(log n) |
| recursive binary search: space | O(log n) stack frames (iterative version: O(1)) |
4.1 Pointers, new/delete & the Heap
&x, *p, p->field | O(1) |
new / delete one object | O(1) (amortised; done by the allocator) |
| Stack memory | automatic: freed when the function returns |
| Heap memory | manual: lives until delete |
4.2 Singly Linked List
| Insert at front | O(1) |
| Insert at end | O(n), or O(1) with a tail pointer |
| Insert at position k | O(k) |
| Delete by value / search | O(n) |
| Access the i-th item | O(n): no random access |
4.3 Doubly Linked List
| Insert / delete at front or end (with tail) | O(1) |
| Delete a node you already have a pointer to | O(1): no need to find prev |
| Search / delete by value | O(n) |
| Traverse backward | O(n): impossible in a singly list without extra memory |
5.1 Stacks with an Array
| push | O(1) |
| pop | O(1) |
| peek / isEmpty / isFull | O(1) |
| search for a value | O(n): not a stack operation |
5.2 Stacks with a Linked List
| push (insert at head) | O(1) |
| pop (delete head) | O(1) |
| peek / isEmpty | O(1) |
5.3 Queues with an Array
| enqueue (at rear) | O(1) |
| dequeue, naive (shift left) | O(n) |
| dequeue, with front index | O(1) |
| front / isEmpty | O(1) |
5.4 Queues with a Linked List
| enqueue (insert after rear) | O(1) |
| dequeue (delete front) | O(1) |
| peek / isEmpty | O(1) |
5.5 Circular Queue
| enqueue | O(1) |
| dequeue | O(1) |
| front / isEmpty / isFull | O(1) |
5.6 std::stack, std::queue & std::deque
| stack push / pop / top | O(1) |
| queue push / pop / front / back | O(1) |
| deque push/pop at either end | O(1) |
| deque d[i] | O(1) |
6.1 Binary Trees & Tree Terms
| count nodes / leaves | O(n): visits every node once |
| height | O(n) |
| find a value (no ordering) | O(n) |
6.2 Binary Search Tree
| search / insert, balanced | O(log n) |
| search / insert, skewed | O(n) |
| min / max | O(h) |
| inorder (sorted output) | O(n) |
6.3 BST Delete (3 Cases)
| delete, balanced | O(log n) |
| delete, skewed | O(n) |
6.4 Tree Traversals
| pre / in / post order | O(n): every node once |
| level order | O(n) |
6.5 General Trees (Left-Child, Right-Sibling)
| visit all nodes | O(n) |
| find the k-th child | O(k) |
| count the children of a node | O(degree) |
7.1 Graph Terminology
| max edges, undirected | V(V − 1)/2 |
| max edges, directed | V(V − 1) |
| sum of all degrees | 2E (each edge counted at both ends) |
7.2 Adjacency Matrix & Adjacency List
| space | matrix O(V²) · list O(V + E) |
| is there an edge u–v? | matrix O(1) · list O(deg u) |
| visit all neighbours of u | matrix O(V) · list O(deg u) |
| add an edge | matrix O(1) · list O(1) |
7.3 Directed Graphs
| out-degree of u | list O(1) (size of adj[u]) · matrix O(V) (row sum) |
| in-degree of u | list O(V + E) · matrix O(V) (column sum) |
| space | matrix O(V²) · list O(V + E) |
7.4 BFS & DFS
| BFS / DFS with adjacency list | O(V + E) |
| BFS / DFS with adjacency matrix | O(V²) |
8.1 Shell Sort
| Best case (sorted) | O(n log n) |
| Average case | depends on the gaps; about O(n^1.5) for n/2, n/4, … |
| Worst case (gaps n/2, n/4, …) | O(n²) |
8.2 Quick Sort
| Best case (pivot splits in half) | O(n log n) |
| Average case | O(n log n) |
| Worst case (sorted input, last-item pivot) | O(n²) |
8.3 Merge Sort
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |
8.4 Heap Sort
| Build heap | O(n) |
| Each extract-max (swap + heapify) | O(log n) |
| Best / average / worst | O(n log n) |
8.5 Hashing Basics
| search / insert / delete, average | O(1) |
| search / insert / delete, worst (all keys collide) | O(n) |