Big O Cheat Sheet
Every cost in one place.
We've met a lot of costs in this course. Here they all are in one place. It's worth pausing on each table, and maybe taking a screenshot.

- Every cost in one place
- Pause on each table
- Keep it handy
Data structures
For lists, indexing and appending are O of one, but searching or inserting at the front is O of N. Dictionaries and sets do lookups, inserts, and deletes in O of one on average. A heap pushes and pops in O of log N, and peeks in O of one. And a balanced tree does everything in O of log N.
| Structure | Fast | Slow |
|---|---|---|
| list | index, append: O(1) | search, insert front: O(n) |
| dict / set | get, add, remove: O(1) | nothing common |
| deque | both ends: O(1) | middle: O(n) |
| heap | peek O(1), push/pop O(log n) | search: O(n) |
| balanced BST | all: O(log n) | none |
Algorithms
Binary search is O of log N. Good sorts are O of N log N, while simple sorts are O of N squared. Breadth and depth first search are O of vertices plus edges, and Dijkstra adds a log factor for the heap. Backtracking can be exponential, which is why we prune.
| Algorithm | Time |
|---|---|
| binary search | O(log n) |
| merge, heap, Timsort | O(n log n) |
| bubble, insertion, selection | O(n²) |
| BFS, DFS | O(V + E) |
| Dijkstra | O((V + E) log V) |
| subsets, backtracking | O(2ⁿ) |
Summary
That's every cost from the course. Lists for order, dictionaries for lookups, heaps for the smallest, and the right algorithm for the job. Next, the final quiz.
Key takeaways- Structure costs
- Algorithm costs
- Pick by the question