~/learn/Python · Algorithms for interviews
Big-O in practice
Estimate cost before you write the code.
why this matters
Interviewers nearly always ask "what's the complexity?". It is also how you predict whether code will survive real data volumes.
Big-O describes how work grows with input size. O(1) constant, O(log n) halving, O(n) one pass, O(n log n) sorting, O(n^2) nested loops. In interviews you are usually asked to get from n^2 to n.
Container costs matter: membership in a list is O(n) but in a set it is O(1). Swapping one for the other is often the whole optimisation.
Try it: Try looking up a value that is not present at all and compare again.
Note
Appending to a list is amortised O(1), but inserting at the front is O(n) — use collections.deque when you need both ends.
Scale at n = 1,000,000
O(1) dict lookup instant O(log n) binary search ~20 steps for 1M O(n) one loop 1M steps O(n log n) sorting ~20M steps O(n²) nested loops 1,000,000M steps
Common gotcha
A loop containing `if x in some_list` is secretly O(n²). Turn the list into a set first.
key takeaways
- Big-O describes growth, not exact seconds.
- Nested loops over the same data are O(n²).
- Swapping a list for a set or dict often removes a whole factor of n.
check your understanding
What is the complexity of a loop over n items that does `if item in a_list` each time?
free practice
Build confidence with a question you can solve without Pro.