Time Complexity in Python Explained: Lists, Sets and Dictionaries

Originally published on CodingCush.

Time complexity in Python tells you how much slower an operation gets as your data grows: looking up a key in a dictionary or checking membership in a set stays roughly constant time, written O(1), while searching a list grows in direct proportion to its length, written O(n). That is why the same code can feel instant with a hundred items and painfully slow with a million. This guide explains the cost of the everyday list, set and dictionary operations in plain words, so you can choose the right container before speed becomes a problem.

First, the Idea in Plain Words

Time complexity is a way of describing how the work grows, not a stopwatch measurement. If an operation is O(1), it takes about the same time whether your collection holds ten items or ten million. If it is O(n), doubling the items roughly doubles the work. If it is O(n²), doubling the items roughly quadruples the work, which is how innocent-looking nested loops turn into long coffee breaks.

If these symbols are new to you, our beginner guide to Big O notation explained simply introduces O(1), O(n), O(n²) and O(log n) with everyday examples first. This post is the practical sequel: it takes those symbols and pins them to the Python operations you actually write every day, using the costs documented for CPython, the standard Python implementation.

List Operations: Fast at the End, Slow in the Middle

names = ["Asha", "Rahul", "Meena"]
names.append("Kiran")        # O(1) - add at the end
names[0]                     # O(1) - read by index
"Kiran" in names             # O(n) - may scan every item
names.insert(0, "First")     # O(n) - everything shifts right
names.pop()                  # O(1) - remove from the end

A Python list is an array of references in a row, which explains its personality perfectly. Reading by index is instant because Python can jump straight to that slot. Appending at the end is fast for the same reason. But inserting at the start forces every existing item to move one place, and searching by value forces Python to look at items one by one until it finds a match or gives up. Neither is a bug; it is simply the price of keeping items in a strict order. Notice that sorting a list costs O(n log n), which is still efficient, and Python's built-in sort is famously fast in practice.

The Python Wiki "Time Complexity" page on wiki.python.org, which documents the cost of list, collections.deque, set and dict operations in CPython.

Set and Dictionary Operations: The Hash Trick

seen = {"asha", "rahul", "meena"}
"rahul" in seen              # O(1) average - hash lookup
seen.add("kiran")            # O(1) average

student = {"name": "Asha", "age": 21}
student["age"]               # O(1) average
student["marks"] = 88        # O(1) average

Sets and dictionaries are fast at finding things because they use hashing. When you add a value, Python computes a short numeric fingerprint of it, called a hash, and stores the value in a bucket chosen by that fingerprint. When you search later, Python computes the fingerprint again and jumps almost directly to the right bucket instead of scanning everything. That is the whole trick, and it is a beautiful one: membership tests, lookups, insertions and deletions are all O(1) on average. The honest footnote is "on average": in rare, unlucky cases many values collide in the same bucket and an operation can degrade towards O(n), but in normal beginner and intermediate code you will simply experience these operations as instant.

This is exactly why our guide to Python data structures: lists, tuples, sets and dictionaries recommends a set whenever the main job is "have I seen this before?" and a dictionary whenever values need labels. The container choice is the optimisation; no clever code afterwards can make a repeated list scan as cheap as a hash lookup.

The Costs Side by Side

Operation	List	Set	Dictionary
Read by position or key	O(1) by index	Not supported	O(1) average by key
Check "is it in there?"	O(n)	O(1) average	O(1) average for keys
Add an item	O(1) at the end, O(n) at the start	O(1) average	O(1) average
Remove an item	O(1) from the end, O(n) from the middle	O(1) average	O(1) average by key
Sort	O(n log n)	Not supported	Not supported
Copy the whole thing	O(n)	O(n)	O(n)

The reference behind this table is the Python Wiki Time Complexity page, which lists the average and worst cases for list, set, dict and deque operations in CPython. Bookmark it: when a program feels slow, checking the cost of your most frequent operation there usually reveals the reason in under a minute.

A Slow Program, Fixed by One Change

# Slow: "in" on a list, inside a loop = O(n) x O(n)
students = [...]          # a list of 50,000 names
present = [...]
for name in students:
    if name in present:   # scans the list every time
        print(name)

# Fast: same logic, set lookup = O(1) each time
present_set = set(present)
for name in students:
    if name in present_set:
        print(name)

This is the most common real-world complexity fix in Python, and it is almost embarrassingly small: convert the list you keep searching into a set, once, before the loop. The loop's logic does not change at all, but each membership test drops from scanning up to 50,000 items to one hash lookup. Programs that took ten seconds suddenly take a blink. Whenever you write in inside a loop, pause and ask what type is on the right side of that in. That one habit prevents most beginner performance bugs.

When a List Is Still the Right Choice

None of this makes lists bad. Lists keep order, allow duplicates, support sorting and slicing beautifully, and are the correct home for anything you mostly read from start to finish. The official Python Tutorial chapter on data structures even shows how to use a list as a stack with append and pop, both O(1), and honestly notes that using a list as a queue is slow because removing from the front is O(n); for queues, it points you to collections.deque, which is built for fast work at both ends. Complexity is not about good and bad containers. It is about matching the container to the operation you repeat most.

Frequently Asked Questions

What does O(1) mean in Python?

It means the operation takes roughly constant time no matter how large the collection is. Dictionary key lookup, set membership tests and list indexing are all O(1) or O(1) on average.

Why is searching a list O(n) but searching a set O(1)?

A list must compare items one by one until it finds a match. A set uses a hash of the value to jump almost directly to where that value would live, so it does not scan the other items.

Is append to a list really O(1)?

Yes, on average. Occasionally the list must grow its internal storage and copy references, but spread across many appends the average cost per append is constant, which is why append is the normal way to build a list.

What is the fastest way to remove duplicates in Python?

Convert the list to a set, which is an O(n) pass that keeps one copy of each value. If the original order matters, build the result with a set for membership checks plus a new list for the order.

Does time complexity tell me the exact speed of my code?

No. It tells you how the cost grows as data grows, not the exact seconds. A simple O(n) loop in Python can beat a complicated O(1) trick for tiny data, but as the data grows, the growth pattern wins.

Conclusion

Lists charge you for searching and for inserting at the front; sets and dictionaries use hashing to make searching, adding and deleting almost free. Learn the table in this post, convert lists you search repeatedly into sets, and reach for a deque for queues. Those three habits will keep your Python programs feeling fast long after your data stops being small.