Big-O Complexity of Python Operations: What list, dict and set Really Cost

A Python solution can be logically correct and still time out because of one harmless-looking line. Put x in a_list or a_list.pop(0) inside a loop, and a solution that seemed linear may become quadratic. Python gives list, dict and set operations similarly clean syntax, but their costs are not similar. The key distinction is the different cost of each operation.

Why "it looks the same" is the trap

Compare x in values with x in seen. If values is a list, Python may inspect every element before answering, so membership is O(n). If seen is a set, membership is O(1) on average. The source lines look almost identical while their growth rates are completely different.

Small examples hide this difference. At 100 elements, even an inefficient scan ends quickly. At 100,000 elements, repeating a scan 100,000 times is a serious amount of work. Timing toy inputs is therefore not enough. You need to identify the operation, know its cost, and then count how often it runs.

If Big-O, Theta and Omega are still blending together, read Time Complexity: Big-O, Theta, Omega & Master Theorem before memorising these costs. Big-O describes how the work grows as the input grows. It does not promise an exact runtime in seconds.

The cost table you should memorise

These are the costs that matter most in coding tests:

A list slice also creates work: a[:k] is O(k), because Python constructs a new list containing k references. del a[i] is O(n) in general because later references shift left, while deleting the last item avoids that shift. Functions such as len(a) are O(1), while min(a), max(a) and sum(a) are O(n) because they must inspect the container. Iterating through a list, dict or set is O(n).

Dict and set operations have an O(n) adversarial worst case when many keys collide. For normal coding-test reasoning, state O(1) average and mention the collision-based worst case if the interviewer asks for it.

One worked example: the same task, O(n) vs O(n^2)

Suppose an array contains n = 100,000 integers and we must decide whether any value appears twice.

Approach A keeps a list:

seen = []
for x in values:
    if x in seen:
        return True
    seen.append(x)
return False

Consider the worst case in which all values are distinct. Before inserting item i, membership can inspect the i earlier items. The total number of element comparisons is:

0 + 1 + 2 + ... + 99,999

Using the arithmetic-series formula, this is 100,000 x 99,999 / 2 = 4,999,950,000 comparisons. A simple n-by-n growth estimate is 100,000 x 100,000 = 10^10 check slots. Both calculations show the same result: the approach grows as O(n^2), and billions of comparisons are far beyond a normal coding-test budget.

Approach B changes only the container:

seen = set()
for x in values:
    if x in seen:
        return True
    seen.add(x)
return False

Each membership test and insertion is O(1) on average. Across 100,000 values, the loop performs about 100,000 membership checks and at most 100,000 additions. That is O(n), not O(n^2). The list version's n-squared growth proxy reaches 10^10 at this input, while the set version's linear proxy reaches 10^5, a 100,000-fold gap between the two growth expressions.

The practical lesson is not that sets are always better. A set does not preserve duplicates and is not the right tool when position or ordering is the point. It is better here because the task asks only about membership.

The costs people get wrong

list.append is O(1) amortised, not O(1) for every single call. A list occasionally needs a larger backing array, and that resize copies existing references. Most appends are constant-time, so the average across many appends remains O(1).

String building has a similar hidden cost. Python strings are immutable. Repeatedly doing result += piece can copy the growing prefix again and again, producing quadratic work. Collect the pieces in a list and call "".join(pieces) once.

Built-ins can also hide a full pass. This loop is quadratic:

for _ in values:
    largest = max(values)

The loop runs n times, and each max scans n elements. That gives n x n work. The fix may be as simple as computing largest = max(values) once before the loop.

Fixing the two classic O(n^2) mistakes

The first repair is membership. When you only need to know whether a value has appeared, replace repeated x in a_list checks with a set. If you need both original order and fast membership, keep the list for order and a separate set for checks.

The second repair is queue behaviour. a_list.pop(0) removes the first reference, then shifts every remaining reference one position left, so it is O(n). insert(0, x) has the same shifting problem. Use collections.deque, whose append, appendleft, pop and popleft operations are O(1).

How this gets tested

Coding platforms use large hidden cases to separate O(n) and O(n log n) solutions from accidental O(n^2) ones. A solution may pass every visible example because those examples test correctness, while the hidden input tests growth.

In an interview, show the reasoning in three steps: name the costly operation, multiply its cost by the number of executions, and replace the container only if the task's semantics allow it. KnowledgeGate's practice bank has over 1,200 algorithm questions, including time-complexity drills that train exactly this habit.

Short version and next step

Remember the dangerous pair: list membership and front insertion are O(n). Dict and set membership are O(1) on average. List append is O(1) amortised, sorting is O(n log n), and a linear built-in inside a linear loop usually creates O(n^2).

Now practise identifying the expensive line before writing the replacement. DSA Using Python gives you a structured route through these choices, while the Coding Skills category helps you place complexity work alongside the rest of your coding preparation.