Big-O in practice

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.

Appending to a list is amortised O(1), but inserting at the front is O(n) — use collections.deque when you need both ends.