Big O describes how the work grows as the input grows, ignoring constant factors:
- O(1): the same work for any size, like a dictionary or set lookup.
- O(n): one pass over the data.
- O(n log n): sorting.
- O(n²): a loop inside a loop over the same data. Ten times the rows means a hundred times the work.
Some loops hide inside one line. x in a_list scans the list, so doing it for every item of another list is O(n²). x in a_set is O(1) on average, so building a set once turns the whole job into O(n). The same goes for list.index, list.count and list.remove inside a loop.
Another trick is to compute once and reuse: running totals answer every "sum from i to j" question with one subtraction.
In this unit, hidden checks use inputs with thousands of items. A quadratic answer runs out of time even when it's correct on small data.