Learn

Your solution has one loop and still runs in quadratic time

24 October 2026 · One mistake, one counterexample

You read the problem, write a short loop, run the example and it passes. You say "this is linear". The interviewer asks what happens with two hundred thousand items, and you realise you never counted the work hidden inside one line. A correct answer with the wrong cost is often marked as a different answer, not a slower version of the right one.

The situation

You are given a list of user ids in the order they logged in, and you must return the first id that appears for the second time, or nothing if none repeats. The list can hold up to 200,000 ids. A natural first version in Python:

def first_repeat(ids):
    seen = []
    for user_id in ids:
        if user_id in seen:
            return user_id
        seen.append(user_id)
    return None

On [7, 3, 9, 3, 7] it returns 3, which is right: 3 is the first id to come back. On an empty list it returns None. There is one for, so it looks linear.

The input that exposes it

Give it ids that never repeat: list(range(200_000)). Nothing is wrong with the answer. The problem is the line user_id in seen. On a list, in walks the list from the start until it finds a match or reaches the end. When nothing repeats, it always reaches the end. The second id checks one element, the third checks two, and the last checks nearly two hundred thousand. That is about n²/2 comparisons, roughly twenty billion for this input.

You can see the shape without waiting for the worst case. Time the function on 10,000, 20,000 and 40,000 distinct ids. Each time the input doubles, the run takes about four times as long. A linear function would take about twice as long. Four times per doubling is the signature of quadratic work.

The hidden assumption is one loop means linear time. It holds only when every line inside the loop costs a constant amount. A membership test on a list does not.

The same thing happens in Java:

static Integer firstRepeat(int[] ids) {
    Set<Integer> seen = new HashSet<>();
    for (int id : ids) {
        if (!seen.add(id)) {
            return id;
        }
    }
    return null;
}

This is the fixed version. The broken one uses a List<Integer> and seen.contains(id), which scans like Python's in. Set.add returns false when the value is already there, so one call does both the check and the insert.

The fix and the invariant

In Python, change one line: seen = set(), and seen.add(user_id) instead of append. A membership test on a hash set takes constant time on average, so the whole function is linear on average, and on 40,000 distinct ids it finishes in a few milliseconds instead of seconds.

The invariant to say is this: the cost of a loop is the number of passes times the cost of the most expensive line inside it. Then name that line. Other common lines that hide a loop: list.pop(0) and list.insert(0, x) in Python, ArrayList.remove(0) in Java, index and count on a list, slicing a list or string inside the loop, and building a string with += in a Java loop.

What to say out loud

Before you code: "The list can have up to 200,000 ids, so I need roughly linear time. A nested scan would be about twenty billion comparisons, which is too slow." When you write the check: "I'm using a set here, because in on a list is a scan, and that would make this quadratic." If you have already written the list version, say it and fix it: "This in is linear on a list, so the whole thing is n squared. Let me switch to a set."

Each sentence takes a few seconds. Together they show the interviewer that your complexity claim covers every line, not just the loops you can see.

The exercise

1. Take three of your own recent solutions, in Java or Python, that you labelled linear.
2. For every line inside a loop, write its cost next to it. Any line that touches a whole list, string or array gets the length of that object, not one.
3. Multiply by the number of passes, and compare the result with what you claimed.
4. For any solution where the claim was wrong, time it on n, 2n and 4n inputs of the worst kind for it, and check whether the run time doubles or quadruples.
5. Rewrite the expensive line, then say the one sentence about the size limit and the structure you chose, aloud, as if you were starting the problem again.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question rather than revealing the solution, so "what does that in cost on a list?" is the kind of question it would put to you. Saying "I'm stuck" gives one more step, up to pseudocode, never finished code.