Foundations
Counting the cost
How to say what an approach costs, and how to read the constraints as a hint about which cost is acceptable.
Key idea
What big-O actually says
Big-O describes how the work grows as the input grows, ignoring constant factors and lower-order terms. O(n) means doubling the input roughly doubles the work. O(n squared) means doubling the input roughly quadruples it.
It deliberately throws away detail, and on small inputs the detail can win. An O(n) method doing 30 operations per element beats an O(n log n) one doing 2 per element only once 30 is smaller than 2 times log base 2 of n, which happens around n = 32,000. Below that the asymptotically worse algorithm is genuinely faster.
Interviewers still ask for the big-O, because it is the part that decides whether your solution survives the largest test case, and the largest test case is usually well past any crossover point like that one.
How to count
Look at the loops. A loop over n items that does constant work per item is O(n). Nesting a second such loop inside it is O(n squared). Loops that run in sequence add, so O(n) then another O(n) is still O(n).
Where log n comes from
A loop that halves the remaining range each pass runs about log base 2 of n times, because that is how many times you can halve n before reaching 1.
That number is much smaller than people expect, which is the whole reason the shape is worth recognizing. Counting it once is more convincing than the formula.
Gotcha
The costs hiding inside one-liners
Python makes expensive operations look cheap. A line with no visible loop can still be linear, and putting one inside a loop is how O(n) solutions quietly become O(n squared).
Space complexity
Space is the extra memory you allocate, not counting the input itself. A hash set holding up to n values is O(n) space. A handful of scalar variables is O(1), no matter how big the input is.
Recursion costs space too, through the call stack. A recursion that goes n levels deep before returning uses O(n) space even if it allocates nothing. That is the answer to why an O(n) recursive solution can still be worse than an O(n) iterative one.
Key idea
The one number to remember
Assume a judge can run on the order of 100 million simple operations per second. That single figure is where the whole table below comes from, and knowing it means you can rebuild the table instead of memorizing it.
Work out roughly how many operations your idea performs on the largest allowed input, and compare it to that budget. Python is several times slower than C or C++, so treat the budget as optimistic here and leave yourself margin.
Tip
Read the constraints as a hint
Problem constraints tell you what complexity is expected. These thresholds follow the ones the USACO Guide publishes, rounded conservatively.
| If n is up to | You can afford | Which usually means |
|---|---|---|
| 10 | O(n!) | Permutations, exhaustive search over orderings |
| 20 to 25 | O(2^n) | Subsets, bitmask over elements |
| 400 | O(n^3) | Triple loop, interval DP, Floyd-Warshall |
| 5,000 | O(n^2) | Every pair, most 2-D DP tables |
| 500,000 | O(n log n) | Sorting, heaps, binary search per element |
| 5,000,000 | O(n) | One pass, hash map, two pointers |
| Astronomically large | O(log n) or O(1) | Binary search, direct formula |
Use this before you write anything. If n can be a million and your first idea checks every pair, that is 10^12 operations, four orders of magnitude past the budget. The idea is dead and you know it in ten seconds rather than after twenty minutes of implementation.
The constraint is not decoration. It is the clearest signal in the problem statement about which solution is wanted.
Key idea
Amortized cost
list.append is documented as O(1), but occasionally a list has to grow its underlying array and copy everything. The copy is O(n), and it happens rarely enough that the average cost per append across many appends is still constant. That average-over-a-sequence-of-operations idea is what amortized means.
It is why you can say appending n items is O(n) total, with a clear conscience, even though individual appends occasionally do far more work.
What does this cost?
Give the time and space complexity of this function in terms of n, the length of nums.
Time
Space
Reading the constraints
A problem states that the array length is at most 200,000 and asks for the number of pairs meeting a condition. Your first idea checks every pair. What should you conclude?
Make it linear
count_duplicates is correct but quadratic: it calls .count() on the list for every element, and each call scans the whole list. Rewrite it to run in one pass using a dict or Counter, keeping the same answer. It returns how many values appear more than once.
Tests
print(count_duplicates([1, 2, 2, 3, 3, 3, 4])) print(count_duplicates([])) print(count_duplicates([5, 5, 5, 5])) print(count_duplicates([1, 2, 3]))
Output
Run the tests when you are ready.