- O(1): constant
- O(n): touch every element in a list once
- Arrays allow fast reads and random access.
- Linked lists allow fast inserts and deletes but only sequential access.
- O(n^2): going through a list of n items n times
- E.g. pushing most played songs into a new sorted array
- Repeatedly finds the min/max element and putting it at the beginning
- Function calls itself
- Recursive case and base case (to avoid stack overflow)
- May take up a lot of memory, function calls go onto the call stack
- O(n log n): average case (stack size is O(log n))
- O(n^2): worst case (stack size is O(n))
- Picking a random pivot and recursively calling quicksort on the two sub-arrays created
- Faster than merge sort (smaller constant)
- Divide and conquer
- O(n log n)
- O(1) time
- Takes up extra space
- Consists of nodes and edges
- Can use BFS if unweighted
- Topological sort: ordered list from graph i.e. A depends on B
- Directed graph: unilateral edge/relationship
- Undirected graph: bilateral (a cycle)
- Check if there is a path and find the shortest path (smallest number of nodes) in an unweighted graph
- Runtime is O(V+E)
- The queue's runtime is O(n); searching the entire graph is at least O(E)
- First in LAST out
- Push and pop
- E.g. matching brackets problem
- First in FIRST out
- Enqueue and deque
- Basically a graph where all edges point one-way only e.g. family tree
- Find the fastest path in a weighted graph
- Only works on directed acyclic graphs (DAGs)
- Cannot be used with negative-weight edges (use Bellman-Ford)
- At each step, pick the locally optimal solution, in the end you're left with the globally optimal solution
- E.g. scheduling problem - pick the event that ends the earliest, pick the event that starts after the first event and ends the earliest.
- Good for approximation algorithms: when calculating the optimal solution will take too much time.
- Problems with no fast algorithmic solution
- How to tell if a problem might be NP-complete:
- "All combinations" or "every possible version"
- Involves a sequence or a set
- Can be restated as the 'traveling salesman' or 'set-covering' problem
- Runs quickly with few items but really slowly with more items
- Problem can be broken into different subproblems
- Involves a grid where each cell is a subproblem
| C | L | U | E | S | |
|---|---|---|---|---|---|
| B | 0 | 0 | 0 | 0 | 0 |
| L | 0 | 1 | 0 | 0 | 0 |
| U | 0 | 0 | 2 | 0 | 0 |
| E | 0 | 0 | 0 | 3 | 0 |
| F | I | S | H | |
|---|---|---|---|---|
| F | 1 | 1 | 1 | 1 |
| O | 1 | 1 | 1 | 1 |
| S | 1 | 1 | 2 | 2 |
| H | 1 | 1 | 2 | 3 |
- Used for classification and regression
- Graph elements based on features and look at k number of nearest neighbours based on distance or cosine similarity
- Machine learning applications like Netflix recommendations, OCR, spam filters
- Rule of thumb: look at sqrt(k) for k number of users/elements
- Trees, B-trees, red-black trees, heaps, splay trees
- Inverted indexes
- Fourier transform
- Parallel algorithms
- MapReduce
- Bloom filters and HyperLogLog
- Secure hash algorithm function
- Locality-sensitive hashing
- Diffie-Hellman key exchange
- Linear programming