Time Complexity of Collection Operations

Roadmaps › Python

Overview

Every Python collection operation has a time complexity — a measure of how the number of steps grows as the collection grows. Big-O notation describes that growth rate: - `O(1)`: Constant time, the same speed regardless of size. - `O(n)`: Linear time, you must scan every element in the worst case. - `O(n log n)`: Log-linear time, typical of efficient sorting algorithms. Think of a `dict` or `set` as a filing cabinet with labelled drawers: you walk straight to the right drawer in `O(1)`. A `list` used for membership testing is an unlabelled pile: you must rifle through every item, `O(n)`. Here are key collection operations and their average-case complexities: - `xs[i]`: Accesses an element by index in a `list` or `tuple` in `O(1)`. Returns the element, or raises `IndexError` if the index is out of bounds. - `list.append(x)`: Adds an item to the end of a `list` in amortised `O(1)`. Returns `None`. - `list.insert(0, x)`: Inserts an item at the beginning of a `list` in `O(n)`. Returns `None`. - `d[key]`: Accesses a value by key in a `dict` in `O(1)`. Returns the value, or raises `KeyError` if the key is missing. - `s.add(x)`: Adds an item to a `set` in `O(1)`. Returns `None`. - `x in c`: Checks if an item exists in a collection. Returns a `bool`. This is `O(1)` for `dict` and `set`, but `O(n)` for `list` and `tuple`. The practical takeaway: whenever you need to check whether a value exists in a collection, convert it to a `set` or use a `dict`. A membership test against a `list` of 1,000,000 items is up to 1,000,000× slower than the same test against a `set`. Example — filtering allowed user IDs from an API request: allowed = {'u-101', 'u-202', 'u-303'} # set, O(1) lookup payload_ids = ['u-202', 'u-999', 'u-101'] valid = [uid for uid in payload_ids if uid in allowed] Example — building a fast cache index: cache = {} # dict, O(1) lookup for record in db_rows: cache[record['id']] = record Removing elements from the front of a `list` is a common performance trap: queue = [1, 2, 3, 4] first_item = queue.pop(0) # O(n) operation! Popping from the front of a `list` is `O(n)` because every remaining element must shift left in memory. If you need a fast queue, use `collections.deque` which offers `O(1)` appends and pops from both ends (covered fully in collections-deque).

Choosing the wrong collection for the job is the most common performance mistake in Python. A single `if item in big_list` inside a loop can silently turn an `O(n)` endpoint into an `O(n²)` endpoint. Understanding these costs lets you pick the right structure before profiling tells you something is slow.

Where used: API response filtering, database query result processing, in-memory caches, Django querysets, FastAPI dependency checks

Why learn this

Code walkthrough

import time

ids = list(range(1_000_000))
id_set = set(ids)
target = 999_999

t0 = time.perf_counter()
target in ids
list_ms = (time.perf_counter() - t0) * 1000

t0 = time.perf_counter()
target in id_set
set_ms = (time.perf_counter() - t0) * 1000

print(f'list: {list_ms:.4f} ms, set: {set_ms:.4f} ms')

Focus: The `set` lookup finishes in microseconds while the `list` scan takes milliseconds — same data, same question, wildly different cost.

Aha moment

data = list(range(100_000))
data_set = set(data)
missing = -1

count = 0
for _ in range(1000):
    if missing in data:
        count += 1

count2 = 0
for _ in range(1000):
    if missing in data_set:
        count2 += 1
print(f'list hits: {count}, set hits: {count2}')

Prediction: Both loops run 1000 iterations and neither finds `-1`. But which loop finishes noticeably slower?

Common guess: They take about the same time because neither finds the item.

Not finding an item in a `list` is the worst case: Python must scan all 100,000 elements every iteration, making 100 million comparisons. The `set` checks a hash bucket and returns immediately each time, finishing almost instantly.

Common mistakes

Glossary

time complexity
A way to describe how the runtime of an operation increases as the amount of data grows, e.g. `O(n)`.
hash collisions
When two different keys accidentally get mapped to the exact same location in a hash table, e.g. `hash('key1') == hash('key2')`.

Recall questions

Understanding checks

A developer thinks that `x in my_list` and `x in my_tuple` have different time complexities because tuples are immutable. Why is this incorrect?

Both lists and tuples are linear sequences without hash tables. Therefore, membership testing (`in`) requires a linear scan (`O(n)`) for both.

Immutability affects whether the structure can change, not how items are looked up. To achieve `O(1)` lookups, a hash table (like in a `set` or `dict`) is required.

Why is inserting an element at the beginning of a list `my_list.insert(0, val)` considered an `O(n)` operation?

Because lists are contiguous arrays in memory. Inserting at the front requires Python to shift every subsequent element one position to the right.

Understanding memory layouts helps predict performance costs. If frequent front-insertions are needed, `collections.deque` is a better choice.

What does this code print?

`True`

Both membership tests correctly evaluate to `False` (so `False == False` is `True`). We use parentheses to avoid Python's comparison chaining rules. The `list` scan is `O(n)` while the `set` check is `O(1)`.

What is the time complexity of the `jobs.pop(0)` call and why?

It is `O(n)`. When an element is removed from the front of a `list`, Python must shift every remaining element left by one position to fill the gap.

Lists are backed by contiguous arrays in memory, making them inefficient for queue-like behaviors where elements are removed from the front.

Practice tasks

Modify List to Set Lookup

The provided function checks for allowed roles using a `list`, making it `O(n)` per check. Modify it to convert the `allowed` roles to a `set` first, so that the lookup inside the loop is `O(1)`.

Challenge

Build a fast request-dedup middleware cache

Write a class `RequestDedup` that stores recently seen request fingerprints (strings). It must support: `add(fingerprint)` to record a request, `is_duplicate(fingerprint) -> bool` to check in `O(1)`, and `clear_older_than(cutoff: float)` that removes entries added before a Unix timestamp. Store each fingerprint with its timestamp. Choose data structures so that `add` and `is_duplicate` are `O(1)` average.

Continue learning

Previous: Lists: indexing, slicing, methods

Previous: Tuples: immutability and use cases

Previous: Dictionaries: operations and use cases

Previous: Sets: operations and use cases

Return to Python Roadmap