Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Data Structures
Time complexity of the basic operations (from the Nov 2023 crash course):
| Data structure | Insert (avg) | Delete (avg) | Search (avg) | Insert (worst) | Delete (worst) | Search (worst) |
|---|---|---|---|---|---|---|
| Array, stack, queue | ||||||
| Linked list | ||||||
| Doubly linked list | ||||||
| Hash table | ||||||
| Binary search tree |
A BST has worst case because it can degenerate into a single chain when values arrive in sorted order.
Heap operations:
- siftdown, insert and delete root:
- heapify (build a maxheap from an array):
Graphs
For a graph with vertex set and edge set (Graph Representations):
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Storage | ||
| Add vertex | ||
| Add edge | ||
| Remove vertex | ||
| Remove edge | ||
| Query (is there an edge?) |
Sorting
| Algorithm (on an array) | Best | Average | Worst |
|---|---|---|---|
| Bubble sort | |||
| Selection sort | |||
| Insertion sort | |||
| Mergesort | |||
| Heapsort | |||
| Quicksort |
Quicksort has the worst worst case of the three fast sorts, but it is often the best practical choice because the constant hidden in its average is very small.
Searching
| Algorithm | Data structure | Worst case |
|---|---|---|
| Sequential search | Array or linked list | |
| Binary search | Sorted array or BST | |
| Depth-first search | Graph with vertices, edges | |
| Breadth-first search | Graph with vertices, edges |