Caveat
The tables in this cheatsheet only make sense after you study all thes mentioned data structures and algorithms below.
Do not memorize them, learn how the underlying algorithms work, read the source.
This cheat sheet is just a quick reference to give an broad brush strokes overview of how the most frequently-used data structures and algorithms relate to each other, in terms of time and space complexity.
| Graph Searching |
|---|
| Space: O(|V|) |
|---|
| time: O( (|V|+|E|) * |V| ) |
|---|
| Dijkstra (using an Array as a priority queue) |
<table style="width:100%">
<tr><th>time: O( (|V|+|E|) * log(|V|) )</th></tr>
<tr><td>Dijkstra (<em>using a Min Heap as a priority queue</em>)</td></tr>
</table>
<table style="width:100%">
<tr><th>time: O(|V|+|E|)</th></tr>
<tr><td>Depth First Search</td></tr>
<tr><td>Breadth First Search</td></tr>
</table>
</td>
</table>
</td>
|
| Binary Search |
|---|
| time: O(log(n)) – space: O(1) |
|---|
| Using a sorted array of n elements. |
|
|
| Sorting |
|---|
| In Place |
|---|
| time: O(n^2) |
|---|
| Bubble Sort |
| Insertion Sort |
| Selection Sort |
|
| time: O(n*log(n)) |
|---|
| Heap Sort |
|
<table>
<tr><th>Not In Place</th></tr>
<tr>
<td>
<table style="width:100%">
<tr><th>time: O(n*log(n)) - space: O(n)</th></tr>
<tr><td>Quick Sort</td></tr>
<tr><td>Merge Sort</td></tr>
</table>
<table style="width:100%">
<tr><th>Other</th></tr>
<tr><th>time: O(n+k) - space: O(nk)</th></tr>
<tr><td>Bucket Sort</td></tr>
<tr><th>time: O(nk) - space: O(n+k)</th></tr>
<tr><td>Radix Sort</td></tr>
</table>
</td>
</tr>
</table>
</td>
</table>
</td>
|
| Data Structures |
|---|
| O(1) indexing - O(n) insert, delete, search |
|---|
| Dynamic Array |
<table style="width:100%">
<tr><th>O(1) insertion and deletion - O(n) indexing, and search</th></tr>
<tr><td>Single Linked List</td></tr>
<tr><td>Doubly Linked List</td></tr>
</table>
<table style="width:100%">
<tr><th>O(log(n)) index, search, insert, and delete</th></tr>
<tr><td>Binary Search Tree</td></tr>
<tr><td>BTree</td></tr>
<tr><td>Red/Black Tree</td></tr>
<tr><td>AVL Tree</td></tr>
</table>
</td>
</table>
</td>
|
| Heaps |
|---|
| Unsorted Linked List |
|---|
| O(1): Increase key, insert, delete, merge |
| O(n): Peek, extract max |
<table style="width:100%">
<tr><th>Sorted Linked List</th></tr>
<tr><td><b>O(1)</b>: Peek, extract max, delete</td></tr>
<tr><td><b>O(n)</b>: increase key, insert</td></tr>
<tr><td><b>O(m + n)</b>: merge</td></tr>
</table>
<table style="width:100%">
<tr><th>Binary Heap</th></tr>
<tr><td><b>O(1)</b>: Peek</td></tr>
<tr><td><b>O(n)</b>: Heapify</td></tr>
<tr><td><b>O(log(n))</b>: Extract max, insert, delete, increase key</td></tr>
<tr><td><b>O(log(m + n))</b>: merge</td></tr>
</table>
</td>
</table>
</td>
|
| Graphs |
|---|
| Adjacency List |
|---|
| O(|V|+|E|): Storage |
| O(1): Add vertex, add edge |
| O(|V|+|E|): Remove vertex |
| O(|E|/|V|): Remove edge (on average) |
| O(|V|): Query |
<table style="width:100%">
<tr><th>Adjacency Matrix</th></tr>
<tr><td><b>O(1)</b>: Add edge, remove edge, query</td></tr>
<tr><td><b>O(|V|^2)</b>: Storage</td></tr>
<tr><td><b>O(|V|^2)</b>: Add vertex, remove vertex</td></tr>
</table>
</td>
</table>
</td>
|
| Big Oh and Its Cousins |
|---|
| Big O |
f(n) <= g(n) |
| Small o |
f(n) < g(n) |
| Big Omega |
f(n) >= g(n) |
| Small omega |
f(n) > g(n) |
| Theta |
f(n) <-> g(n) |
|
|
| | | | |
