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)

v0lkan/dsaqdcs.md