Big-O of common operations
Big-O describes how running time grows with input size n, ignoring constants. Typical costs: hash map (Python dict and set) lookup, insert and delete are O(1) on average; searching an unsorted list is O(n); binary search on a sorted array is O(log n); heap push and pop are O(log n) while reading the minimum is O(1); good general-purpose sorting is O(n log n); nested loops over the same input are O(n^2). A practical rule: around 10^5 items, O(n^2) is roughly 10^10 operations and will time out, while O(n log n) or O(n) finishes instantly.
When an interview problem mentions large inputs, that is a hint to replace a nested loop with a hash map, a sort, a heap or two pointers.
Check yourself