Counting the cost

How to say what an approach costs, and how to read the constraints as a hint about which cost is acceptable.

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).

Python

1# O(n): one pass2for x in nums:3    total += x4 5# O(n squared): every pair6for i in range(len(nums)):7    for j in range(i + 1, len(nums)):8        check(nums[i], nums[j])9 10# still O(n): two passes in sequence, not nested11for x in nums:12    total += x13for x in nums:14    largest = max(largest, x)

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.

1# O(log n): however you halve, this is how many passes you get2remaining = 1_000_0003passes = 04 5while remaining > 1:6    remaining //= 27    passes += 18 9print(passes, "passes to get from a million down to one")

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).

Python

1# Each of these is O(n) on its own2if target in nums: ...        # list membership scans3sub = s[i:]                   # slicing copies4smallest = min(nums)          # one full pass5nums.pop(0)                   # shifts everything6 7# So this is O(n squared), not O(n)8for i in range(len(nums)):9    if nums[i] in seen_list:  # linear scan inside a linear loop10        ...

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.

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.

Complexity· 5 min

What does this cost?

Give the time and space complexity of this function in terms of n, the length of nums.

Python

1def has_pair_with_sum(nums, target):2    for i in range(len(nums)):3        for j in range(i + 1, len(nums)):4            if nums[i] + nums[j] == target:5                return True6    return False

Complexity· 5 min

What does this one cost?

Careful. There is no nested loop written here, but look at what each line actually does.

Python

1def build_suffixes(s):2    result = []3    for i in range(len(s)):4        result.append(s[i:])5    return result

Quick check· 5 min

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?

Implement it; 200,000 is small enough for a double loopRoughly 2 times 10^10 pair checks is far too many, so the constraint is telling you to find an O(n) or O(n log n) approachImplement it and add an early exit, which will bring it under the limitThe constraint says nothing about the intended complexity

Refactor· 10 min

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.

solution.py

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 tests to see output.

CodeGround