AI Hints
Home›DSA in Python Tutorial›Interview Questions
DSA in Python · Lesson 129 of 132

Big O Cheat Sheet

Every cost in one place.

⏱ 2 min read▶ Video at 2:34:05🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Big O Cheat Sheet
From the video: Big O Cheat Sheet
  • 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.

StructureFastSlow
listindex, append: O(1)search, insert front: O(n)
dict / setget, add, remove: O(1)nothing common
dequeboth ends: O(1)middle: O(n)
heappeek O(1), push/pop O(log n)search: O(n)
balanced BSTall: 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.

AlgorithmTime
binary searchO(log n)
merge, heap, TimsortO(n log n)
bubble, insertion, selectionO(n²)
BFS, DFSO(V + E)
DijkstraO((V + E) log V)
subsets, backtrackingO(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
Next up: Final Quiz — test everything