Skip to content

Instantly share code, notes, and snippets.

@v0lkan
Last active January 14, 2023 23:22
Show Gist options
  • Save v0lkan/1e1f3e7e233803db56ed to your computer and use it in GitHub Desktop.
Save v0lkan/1e1f3e7e233803db56ed to your computer and use it in GitHub Desktop.
Data Structures and Algorithms Quick And Dirty Cheat Sheet

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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment