Python time complexity is the reason two programs that produce identical results can finish in five milliseconds or twenty-seven seconds, and the difference usually comes down to which container you reached for. This post takes the four workhorse structures, list, dict, set, and tuple, and shows you exactly what each operation costs by running real timeit measurements, so you stop guessing and start picking the right tool on purpose.

“The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly.”

Donald Knuth, The Art of Computer Programming

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Intermediate | Reading Time: 18 minutes

Here is the everyday version. Say a user named Aditi hands you a stack of a thousand receipts and asks, “is this one in the pile?” If the receipts are in a shoebox, you flip through them one at a time until you find it or reach the bottom. If instead they are filed in labeled folders by receipt number, you walk straight to the right folder in one move. Same question, wildly different effort, and the only thing that changed was how the receipts were organized. A Python list is the shoebox. A set or dict is the filing cabinet. Everything in this post is that one idea, measured.

If you have read the Big O tutorial, you already know the vocabulary: O(1) is a single hop, O(n) is a full walk. Here we pin those labels onto the actual containers you use every day and prove the cost with a clock. The details of how CPython 3.14.6 lays out a dict in memory are current at the time of writing, but the concept, jump to the item versus scan for it, is portable to every language you will ever touch.

Why the Container You Pick Decides Your Speed

Every container in Python is a trade. A list keeps items in order and lets you index by position instantly, but finding a value means scanning. A dict and a set give up nothing on lookup speed because they use a hash table, but they cost a little memory and cannot be indexed by position. A tuple is a frozen list: same access shape, but immutable and hashable. The table below is the Python time complexity cheat sheet. Keep it next to you and most performance decisions answer themselves.

The starred O(1)* entries are amortized, meaning the occasional internal resize is averaged out so the typical add is constant. The two bold O(n) rows are where beginners get burned: membership on a list and inserting at the front of a list both walk the collection. The rest of this post is about recognizing those moments and swapping in the structure that turns them into a single hop.

List vs Set at Ten Million Items

The table says list membership is O(n) and set membership is O(1), but a table never changes anyone’s habits. A stopwatch does. Let’s build a list and a set that each hold ten million integers, then ask both the same question: “is this value present?” To make it a fair worst case, we ask for a value that is not there, so the list is forced to scan every single element before giving up.

📄 membership.py: the same lookup on a list and a set, 10M items

import timeit

n = 10_000_000
data_list = list(range(n))
data_set = set(data_list)

# Worst case: the item is NOT there, so a list scan must walk everything
target = -1

t_list = timeit.timeit(lambda: target in data_list, number=5) / 5
t_set = timeit.timeit(lambda: target in data_set, number=5) / 5

print(f"items: {n:,}")
print(f"list  'in' : {t_list*1e3:>10.4f} ms")
print(f"set   'in' : {t_set*1e9:>10.1f} ns")
print(f"set is {t_list/t_set:,.0f}x faster")

▶ Output

items: 10,000,000
list  'in' :   109.3437 ms
set   'in' :      440.0 ns
set is 248,507x faster

What happened here: The list took about 109 milliseconds to answer one question. The set took 440 nanoseconds, which is 440 billionths of a second. That is not a typo, the set is roughly 248,000 times faster for this single lookup. The list has to compare against value after value until it reaches the end, so its cost grows with the size of the data. The set computes a hash of -1, jumps to the one bucket where that value would live, sees it is empty, and answers “no” without touching the other ten million items. Notice the units in the output: milliseconds for the list, nanoseconds for the set.

Your exact multiplier will vary by machine, but the gap is always enormous, and it only widens as the data grows. This is the single most valuable performance fact in everyday Python.

How a Dict Works Under the Hood

So how does a set or dict pull off that one-hop lookup? The trick is a structure called a hash table. Think of a hotel with numbered pigeonhole mailboxes behind the front desk. When a letter arrives for room 214, the clerk does not read every box, they compute “214” and walk straight to that slot. A dict does the same thing: it runs your key through a hash function to get a big number, squeezes that number down to a slot index, and stores the value there. Looking it up later repeats the same calculation and lands in the same place.

Tip: click the diagram to open it full screen, then use the zoom and pan controls for a closer look.

Two keys can occasionally squeeze down to the same slot, which is called a collision. When that happens, Python does not panic, it simply probes to the next available slot and remembers where the key really landed, checking the actual key on the way out so it never confuses one for another. Let’s watch the hashing step in the open. Because CPython randomizes string hashing per process for security, this script pins the seed with PYTHONHASHSEED=0 so the numbers are reproducible for you.

📄 hashing.py: run with PYTHONHASHSEED=0 py -3.14 hashing.py

keys = ["paneer", "rice", "dal", "roti"]

n_buckets = 8   # a tiny table, real dicts start at 8 and grow
print(f"{'key':>8} | {'hash(key)':>22} | bucket = hash % {n_buckets}")
print("-" * 52)
for k in keys:
    h = hash(k)
    print(f"{k:>8} | {h:>22} | {h % n_buckets}")

▶ Output

     key |              hash(key) | bucket = hash % 8
----------------------------------------------------
  paneer |    6436641448954418703 | 7
    rice |    5971047564312733763 | 3
     dal |   -3662758688361773051 | 5
    roti |   -1480015606323375521 | 7

What happened here: Each key becomes a large, unpredictable integer through hash(), and then hash % 8 squeezes it into one of eight buckets. Notice that paneer and roti both landed in bucket 7, a real collision. A real dict starts with eight slots and grows itself long before it gets crowded, keeping collisions rare, which is why the average lookup stays O(1) even though a worst-case pile-up is theoretically O(n).

One important caveat this demo exposes: only hashable values can be keys, and only immutable things are hashable. A string, number, or tuple can be a dict key or a set member; a list or another dict cannot, because their contents could change and move the item to a different bucket after it was filed. That single rule explains most “unhashable type” errors you will ever see.

When Lists Fall Apart

Lists are excellent until you ask them to do two specific things: insert at the front, or stay sorted while you keep adding. Both quietly become O(n) and drag your program down. The good news is the standard library has a purpose-built answer for each.

First, the front-insert problem. Picture a queue at a sabzi stall where every new customer insists on standing at the very front. Everyone already in line has to shuffle back one step, every single time. That shuffle is what a Python list does when you insert(0, x): it moves all existing elements up one slot. A collections.deque (double-ended queue) is built for exactly this, adding to either end in constant time.

📄 frontinsert.py: list.insert(0, x) vs deque.appendleft

import timeit
from collections import deque

print(f"{'n':>9} | {'list.insert(0,x)':>18} | {'deque.appendleft':>18}")
print("-" * 52)
for n in [10_000, 20_000, 40_000, 80_000]:
    t_list = timeit.timeit(
        "lst.insert(0, 1)",
        setup=f"lst=list(range({n}))",
        number=2000) / 2000
    t_deque = timeit.timeit(
        "dq.appendleft(1)",
        setup=f"from collections import deque; dq=deque(range({n}))",
        number=2000) / 2000
    print(f"{n:>9,} | {t_list*1e6:>15.3f}us | {t_deque*1e9:>15.1f}ns")

▶ Output

        n |   list.insert(0,x) |   deque.appendleft
----------------------------------------------------
   10,000 |           6.051us |            30.4ns
   20,000 |          11.473us |            31.3ns
   40,000 |          22.073us |            29.1ns
   80,000 |          44.654us |            29.3ns

What happened here: Read the list column top to bottom: 6us, 11us, 22us, 44us. Every time the list doubles in size, the front-insert takes twice as long, because it has to shift twice as many elements. That is O(n) behavior in plain sight. The deque column stays flat at around 30 nanoseconds no matter how big it gets, because it just clips the new item onto the front link. At 80,000 items the deque is already over a thousand times faster for this operation, and the gap grows without bound. If your code repeatedly adds or removes from the front, reach for a deque and the problem disappears.

The second list weakness is keeping things in sorted order. Re-sorting the whole list after every insert is wasteful, and scanning to find “how many items are below X” is a linear count. The bisect module fixes both by using binary search on an already-sorted list, an O(log n) operation, to find the right spot or count in a handful of steps. Sorting itself has its own cost story, and the sorting algorithms guide explains why the good ones all land at O(n log n).

📄 bisect_demo.py: find, insert, and count in sorted order

import bisect

# A price list kept sorted. We want the position of a new price
# without re-scanning or re-sorting the whole thing.
prices = [40, 55, 55, 70, 90, 120]

# Where would 60 go to keep the list sorted? (O(log n), not O(n))
pos = bisect.bisect_left(prices, 60)
print("insert 60 at index:", pos)

# Insert it while preserving order, in one call
bisect.insort(prices, 60)
print("after insort      :", prices)

# "How many items cost 55 or less?" is now a binary search, not a count loop
count_le_55 = bisect.bisect_right(prices, 55)
print("items <= 55       :", count_le_55)

▶ Output

insert 60 at index: 3
after insort      : [40, 55, 55, 60, 70, 90, 120]
items <= 55       : 3

What happened here: bisect_left found that 60 belongs at index 3 without touching every element, using binary search to halve the search range each step. insort then placed it there while keeping the list sorted, and bisect_right answered “how many items are 55 or less” as 3, again in log-time rather than a full count. On a sorted list of a million prices, bisect answers in about twenty comparisons where a naive scan would need up to a million. Keep a list sorted with bisect and you get fast range queries almost for free.

Choosing the Right Structure: Six Scenarios

Python time complexity rules are easier to apply when they are tied to concrete jobs. Here are six tasks you will meet constantly, with the structure that turns each from painful to trivial. This is a reference list, not program output, so read it as a decision guide.

The pattern to notice: whenever the job is “look something up,” “have I seen this,” or “map A to B,” the answer is a hash-based structure and the cost is O(1). Whenever it is “add and remove at the ends,” it is a deque. Lists remain the right default when you mostly append and iterate in order, which is still the majority of code.

The Why Is My Code Slow Story

Let’s turn this into a real debugging story, the kind that lands in an actual code review. Say a developer named Anvay writes a function that finds which paid orders also shipped, the overlap between two lists of order IDs. It passes every test on small sample data and then times out on the nightly run over the full dataset. The logic is correct, so what went wrong? The answer is a single hidden O(n) inside a loop, and the fix is one line.

📄 slowstory.py: list-scan intersection vs set-lookup intersection

import timeit, random

# Two lists of order IDs. We want the orders that appear in BOTH:
# paid orders that also shipped. Classic "intersection" job.
random.seed(7)
paid = [random.randint(0, 500_000) for _ in range(50_000)]
shipped = [random.randint(0, 500_000) for _ in range(50_000)]

# SLOW: for each paid id, scan the whole shipped LIST -> O(n * m)
def both_slow(paid, shipped):
    out = []
    for oid in paid:
        if oid in shipped:      # 'in' on a list = full scan every time
            out.append(oid)
    return out

# FAST: build a set once, then each lookup is O(1) -> O(n + m)
def both_fast(paid, shipped):
    shipped_set = set(shipped)
    return [oid for oid in paid if oid in shipped_set]

t_slow = timeit.timeit(lambda: both_slow(paid, shipped), number=1)
t_fast = timeit.timeit(lambda: both_fast(paid, shipped), number=1)

# Sanity check: both return the same matches
assert set(both_slow(paid, shipped)) == set(both_fast(paid, shipped))

print(f"list scan (O(n*m)) : {t_slow*1e3:>9.1f} ms")
print(f"set lookup (O(n+m)): {t_fast*1e3:>9.2f} ms")
print(f"speedup            : {t_slow/t_fast:>9.0f}x")

▶ Output

list scan (O(n*m)) :   26848.3 ms
set lookup (O(n+m)):      5.00 ms
speedup            :      5372x

What happened here: The slow version took nearly 27 seconds; the fast version took 5 milliseconds, a 5372x speedup, and both return exactly the same orders (the assert proves it). The only change was building set(shipped) once and testing membership against the set instead of the list. In the slow version, oid in shipped scans up to 50,000 elements, and it does that 50,000 times, which is 2.5 billion comparisons.

In the fast version each check is a single hash lookup, so the whole job is one pass to build the set plus one pass to test, and it finishes before you blink. This exact swap, list to set for the thing you look up repeatedly, is the most common real-world Python speedup there is. When someone asks “why is my code slow,” look for a membership test on a list inside a loop first.

Common Mistakes

❌ Mistake: rebuilding a set inside the loop

# Bad: set(b) is rebuilt on every iteration -> back to O(n * m)
def common(a, b):
    return [x for x in a if x in set(b)]   # set(b) runs once per x!

# Good: build the set a single time, outside the loop
def common_fast(a, b):
    b_set = set(b)                         # one O(n) build
    return [x for x in a if x in b_set]    # each check O(1)

Why: Converting to a set is the right instinct, but doing it inside the comprehension rebuilds the entire set for every element of a, which throws away the whole benefit and can even be slower than the plain list scan. Build the set once, above the loop, and reuse it. The rule is simple: any O(n) setup work belongs outside the loop that uses it.

❌ Mistake: using a list as a dict key

seen = {}
key = [1, 2]
seen[key] = "value"     # TypeError: unhashable type: 'list'

# Fix: use an immutable tuple as the key instead
seen[(1, 2)] = "value"  # works, tuples are hashable

Why: A dict key and a set member must be hashable, and only immutable objects are hashable. A list can change after you store it, which would move it to a different bucket and lose it, so Python refuses outright. Swap the list for a tuple of the same values and the error vanishes. This is the reason coordinates and composite keys are almost always tuples.

Best Practices

• Default to a set for membership. If your code asks “is X in here” more than once, store the collection as a set or the keys of a dict, not a list. This one habit prevents most accidental quadratic code.
• Use a deque for front operations. Any queue, sliding window, or “add to the front” pattern belongs in collections.deque, which makes both ends O(1).
• Keep expensive builds out of loops. Building a set or dict is O(n); do it once above the loop, never per iteration.
• Reach for the specialized tools. collections.Counter for counting, bisect for sorted lookups, functools.lru_cache for caching. They are tested, fast, and clearer than hand-rolled versions.
• Measure on realistic sizes. A list is fine at ten items and disastrous at ten million. Use timeit on data the size you actually expect before deciding the structure matters.

Wrapping Up

Python time complexity stops being abstract the moment you tie it to containers. A list is a shoebox: perfect for keeping order and appending, but O(n) to search or to insert at the front. A dict and a set are filing cabinets backed by a hash table: O(1) to look up, at the cost of needing hashable keys. A deque handles both ends in constant time, and bisect keeps a list searchable in log-time.

You watched a set beat a list by 248,000x on a single lookup, saw a deque hold flat while a list crept upward on front inserts, and turned a 27-second function into a 5-millisecond one by changing one word from list to set. None of this depends on the framework of the month. The mechanics of CPython 3.14.6 are current at the time of writing, but the core idea, jump to the item instead of scanning for it, will outlive every version and port to every language.

Next in this chapter we move from picking the right structure to finding the slow spot in the first place, with profilers that point straight at the line costing you time. every lesson in reading order is listed on the Python + AI/ML tutorial series home.

Frequently Asked Questions

Interview Questions on Python Time Complexity

How interviewers actually probe this topic: real scenarios, with answers you can say out loud.

Q: Your function checks if x in results inside a loop and times out on the largest input. What is the complexity and how do you fix it?

If results is a list, x in results is O(n), and running it inside a loop over n items makes the function O(n squared), which is what blows up on the biggest case. The fix is to keep results as a set, or maintain a separate seen set, so each membership check drops to O(1) and the whole function becomes O(n). This is the single most common interview rescue.

Q: How do you find the common elements of two large lists efficiently?

Convert both to sets and use the intersection operator: set(a) & set(b). Building each set is O(n), and the intersection is proportional to the smaller set, so the whole thing is linear. The naive approach of a nested loop or x in b on a list is O(n times m), which we measured at nearly 27 seconds versus 5 milliseconds for the set version on 50,000-item inputs.

Q: What makes an object usable as a dict key or set member?

It must be hashable, which in practice means immutable: numbers, strings, and tuples of immutables qualify, while lists, sets, and dicts do not. Hashability lets Python compute a stable bucket for the object; a mutable object could change after storage and become unfindable, so Python raises “unhashable type” rather than risk it. A frozenset is the immutable, hashable version of a set for exactly this reason.

Q: A dict lookup is “O(1),” yet the worst case is O(n). Explain.

Average lookup is O(1) because the hash spreads keys across many buckets, so each bucket holds very few items. The worst case is O(n) if every key hashes into the same bucket and Python must probe through all of them. In practice this almost never happens: the table resizes to stay sparse and the hash function distributes keys well, so O(1) average is the number you plan around.

Q: You need a fixed-size queue that drops the oldest item when full. What do you use and why?

A collections.deque(maxlen=k). Appending past the max length automatically evicts from the opposite end, and both ends are O(1), so it is perfect for sliding windows and recent-history buffers. A list would force an O(n) pop(0) for every eviction, turning a constant-time operation into a linear one.

Q: When is a plain list still the best choice despite O(n) search?

When you mostly append and iterate in order, when the data is small enough that O(n) is trivially fast, or when you need positional indexing and ordering that a set cannot give. Lists have the lowest overhead and clearest semantics for sequential data; the switch to a set or dict pays off specifically when repeated lookups by value dominate.

Want more? the official Python documentation documents everything this post could not fit.

Related Posts

Previous: Big O Notation in Python, Explained with Real Timings

Next: Sorting and Searching Algorithms in Python (From Scratch)

Series Home: Python + AI/ML Tutorial Series